[6588번] 골드바흐의 추측

📌풀이

에라토스테네스의 체를 사용해 푸는 문제인 것 같다. 에라토스테네스의 체는 아래와 같은 방식으로 진행된다. 가장 작은 소수인 2부터 자신의 배수들을 지워나가면서 소수를 찾아낸다.

📌코드

#include <stdio.h>
#include <stdbool.h>

int main()
{
    int input = -1, minus = 0;
    bool prime[1000000];

    for(int i=2; i<=1000000; i++)
    {
        if(!prime[i])
        {
            for(int j=i*2; j<=1000000; j+=i)
            {
                prime[j] = true;
            }
        }
    }

    while(input)
    {
        scanf("%d", &input);
        if(!input)
            break;
        for(int i=3; i<=input; i++)
        {
            if(!(prime[i]|prime[input-i]))
            {
                printf("%d = %d + %d\n", input, i, input-i);
                break;
            }
        }
   }
    return 0;
}

삽질을 개만이 했다. 2시간 정도 걸렸는데 이유는

 

1. 에라토스테네스의 체를 이해하는 데에 시간이 오래 걸림.

2. 그걸 코드로 옮기는 데에도 시간이 오래 걸림.

3. 계산된 prime 배열을 초기화 하지 않아서 실행 시마다 다른 결과값이 나오게 됨.

4. 그래서 prime 배열을 미리 계산한 뒤 입력된 값의 소수들을 찾는 방법을 채택함.

 

여기까지 오는 시간이 오래 걸렸기 때문이다!

하지만 어쨌든 풀어냈다는게 핵심임. 해냈다!

 

아 그리고 문제에는

• 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

라고 되어 있는데 코드를 보면 알겠지만 내 코드에는 해당 문자열을 출력하는 코드가 없다. 그런데도 맞았음. 저 코드를 출력할 수 있는 반례가 없어서 그런걸까?