6588_골드바흐의 추측

 소수 구하기 살짝 응용이 된 문제로, N^2의 방법으로는 이 문제를 풀 수 없다. 문제를 간단히 설명하자면, 4보다 큰 짝수는 모두 소수의 합으로 표현 될 수 있다는 골드바흐의 추측을 근거로 짝수를 소수의 값으로 표현해보는 것이이다. 이 때 짝수 n의 범위는 6 ≤ n ≤ 1000000 이다. 그러므로 시간초과를 피하기 위해서는 O(n)으로 해결해야 한다. 

  

 우선, 에라토스테네스를 통해 1000000까지의 소수값을 한 번에 구한다. 나는 모르고 n을 할 때마다 소수값을 구해서 굉장히 오랜 시간이 걸렸는데 미리 소수값을 구해놓으면 시간이 더 이상 들지 않는다.

그럼 이제 에라토스테네스의 시간복잡도를 고려했야 하는데 에라토스테네스의 시간 복잡도는 O(n log log n) 이라고 한다. (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity)

 

에라토스테네스 부분 코드

int prime[1000001];
void getPrime(int n){
    prime[0] = 1;prime[1] = 1;
    for(int i = 2; i <= n;i++){
        if(prime[i]) continue;
        for(int j = i * 2;j <= n; j += i){
            prime[j] = 1;
        }
    }
}

에라토스테네스는 소수의 배수를 이용해 소수의 배수들을 가지치기 하면서 소수만을 남겨놓아 구하는 방식이다. 

 

다음으로 전체 코드이다.

전체 코드

#include<bits/stdc++.h>
 
using namespace std;
 
int prime[1000001];
void getPrime(int n){
    prime[0] = 1;prime[1] = 1;
    for(int i = 2; i <= n;i++){
        if(prime[i]) continue;
        for(int j = i * 2;j <= n; j += i){
            prime[j] = 1;
        }
    }
}
 
int main(void){
    int n, a, b;
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    getPrime(1000000);
    while(cin >> n){
        if(n == 0) break;
        for(int i = 2; i <= (n / 2); i++){
            if(prime[i] == 0 && prime[n - i] == 0){
                a = i; b = n - i; break;
            }
        }
        cout << n << " = " << a << " + " << b << "\n";
    }
 
}