Algorithm) BOJ) 백준 6588 - 골드바흐의 추측

문제 보러 기기

6588번: 골드바흐의 추측

 

주어진 짝수를 두 소수 홀수의 합으로 나타내는 문제이다. 문제는 두 홀 수를 a, b라 할 때, b-a가 가장 적어야 한다는 것이다.

한마디로 주어진 수 N - a(홀수 소수) = b(홀수 소수) 가 되는 가장 작은 a를 찾는 것이다. 

 

가장 작은 홀수 소수는 3이니 3부터 시작하면 될텐데.. n = 1000000 이라면

999997가 소수인지 아닌지를 알아야 한다... 

 

그러니 3 ~ 1000000 까지의 소수를 모두 구해놓으면 간단한 문제이다.

 

이 문제의 핵심은 시간이다.

 

여기서 에라토스테네스의 체 개념이 나오는데, 간단하게 설명하면,

 

2부터 시작해 살아있는 수의 배수를 모두 지워 나가면 소수만 남게 된다는 것이다.

 

2부터 100까지의 소수를 구하고자 한다면,

 

2는 살았으니 두고, 2의 배수 4, 6, 8, ..., 100 까지를 모두 지운다.

3은 살았으니 두고, 3의 배수 3, 9, ... , 99 까지를 모두 지운다.

4는 지워졌고,

5는 살았으니 두고, 5의 배수 5, 15, 25, ..., 100 까지를 모두 지운다.

 

6같은 경우 2의 배수에서 이미 지워졌으니 3에서는 체크할 필요가 없다.  

여기서는 무조건 짝수 n만 주어지니 짝수는 생각하지 않고 홀 수만 생각해도 되긴 하지만,

이미 2의 배수에서 모든 짝수는 지워지기 때문에 시간에는 크게 영향을 미치지 않는다.

 

이 문제의 핵심은 

살아있는 수를 체크해 나가는 변수를 i라 할 때, i 다음에는 바로 ixi 의 수부터 i의 배수만 확인하면 된다는 사실이다.

 

7을 예로 들어보면,

7은 소수이고, 49부터 그 다음 7의 배수인 56, 64, ... 를 지워나가면 된다.

사실 56, 64는 그 전에 모두 지워졌으니 7, 49, 77, 91 순으로 지워나갈 수 있게 된다. 

 

여기서 추론할 수 있는 사실은 i x i 가 n을 넘어서면 이미 n까지는 그 이전에 모두 확인이 되었기 때문에 그만해도 된다는 사실.

( 이게 수가 커지면 엄청난 차이가 있다. )

 

사실 이 문제는 어마어마하게 혈투(?) 를 벌였다 . . . 

........

 

이 문제는 0을 입력받을 때까지 계속해서 Input이 주어지는 문제다.

 

처음에 2 ~ 1000000 의 소수를 모두 구해놓고 확인하면 되는데

매번 입력을 받을 때 마다 n까지의 소수를 구해서 계속 시간초과가 났었다. ㅠㅠ.....

 

그래서 최종적인 코드는 다음과 같다. 

 

Swift 풀이

func getPrime(_ n: Int) -> [Bool] {
    
     var boolPrimes = [Bool](repeating: true, count: n+1)

     for i in 2...n {
          if i*i >= n {
               break
          }
          
          if boolPrimes[i] {
               for j in stride(from: i*i, to: n+1, by: i) {
                    if boolPrimes[j] {
                         boolPrimes[j] = false
                    }
               }
          }
     }
   
     return boolPrimes
}



while let input = readLine().map({Int($0) ?? 0}), input != 0 {
     let primes = getPrime(input)
     for i in stride(from: 3, to: input+1, by: 2) {
          if primes[i] {
               let temp = input - i
               if primes[temp] {
                    print("\(input) = \(i) + \(temp)")
                    break
               }
          }
    }
}

 

 

C++ 풀이

#include <iostream>
const int MAX = 1000000;
bool primes[MAX+1];


void getPrimes(int n) {

    for(int i=2; i*i<=MAX; i++) {
        if (primes[i] == false) {
            for(int j=i*i; j<=MAX; j+=i) {
                primes[j] = true;
            }
        }

    }

}

int main(int argc, const char * argv[]) {

    getPrimes(MAX);


    while (1) {
        int n;
        scanf("%d", &n);
        if (n == 0) {
            return 0;
        }
        for (int i=2; i<=MAX; i++) {
            if (!primes[i]) {
                int temp = n-i;
                if (primes[temp] == false) {
                    printf("%d = %d + %d\n", n, i, temp);
                    break;
                }
            }
        }
    }
    
    return 0;
}