백준 6588번 골드바흐의 추측 - C++ 풀이

---

 

1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다.

 

1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다.

 에라토스테네스의 체를 이용하여 백만 이하의 모든 소수를 구한다. n이하의 모든 소수 i에 대해 n-i가 소수인지 판별하면 된다. 이때 i를 오름차순으로 순회하고, 답이 나올 경우 순회를 종료시키면 b-a가 가장 큰 답을 구할 수 있다.

 백만 이하의 소수 개수는 약 8만 개이므로, 이 풀이의 시간 복잡도는 O(80,000*T)이다. 이때 T(테스트 케이스 수)가 10^5이므로 시간 초과가 날 것 같았는데 시간 초과가 나지 않았다. 이에 관련된 질문과 답을 아래 게시글에서 발견하였다.

글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요?

 

반응형

---

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<bool> is_prime(1000001, true);
vector<int> primes;

void calcPrimes() {
    for (int i=2; i<=1e6; i++) {
        if (!is_prime[i]) continue;
        
        int temp = i*2;
        while (temp <= 1e6) {
            is_prime[temp] = false;
            temp += i;
        }
    }
    
    for (int i=2; i<=1e6; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}

string solution(int n) {
    for (auto prime: primes) {
        if (prime >= n) return "Goldbach's conjecture is wrong.";
        
        if (is_prime[n-prime]) {
            return to_string(n) + " = " + to_string(prime) + " + " + to_string(n-prime);
        }    
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    calcPrimes();
    
    while (true) {
        int n; cin >> n;
        if (n == 0) break;
        cout << solution(n) << "\n";
    }

    return 0;
}