[C++] 백준 6588번: 골드바흐의 추측 (소수)

https://www.acmicpc.net/problem/6588

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

자연수 n, 홀수 소수 a, b에 대해 n = a + b를 만족시키는 a, b를 구하여라. 답이 여러 개인 경우에는 b - a가 가장 큰 것을 출력한다.

---

시간복잡도 어림하기

소수 구하기

  소수를 구하는 문제는 일반적으로 에라토스테네스의 채를 사용합니다. 에라토스테네스의 채를 사용해야하는 이유는 아래 문제 풀이에서 확인하실 수 있습니다.

[C++] 백준 4948번: 베르트랑 공준 (소수)

---

알고리즘 설계하기

 자연수 n이 어떤 두 소수의 합으로 이루어지는지 찾는 문제입니다. 문제에서는 두 홀수 소수의 합이라고 했으므로 3이상인 소수를 찾으면 됩니다.

 

 자연수 n이 어떤 두 소수의 합인지 찾는 것은 간단합니다. n = a + b에서 a값이 결정되면 b값은 자동으로 결정되기 때문에, a가 소수일때, b도 소수인지를 확인하면 쉽게 찾을 수 있습니다.

 이때, a, b값이 여러 개인 경우에는 b - a값이 가장 큰 것, 다시말해 a값이 가장 작은 것을 골라야 합니다. 이는 i = 3부터 n / 2까지 탐색하면서 가장 먼저 조건을 만족하는 a, b값을 찾으면 가장 차이가 큰 답입니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int n, a[1000004], flag;
int main(){
	/*소수 구하기(에라토스테네스의 채)*/
    for(int i = 2; i <= 1000000; i++){
        if(a[i]) continue;
        for(int j = i + i; j <= 1000000; j += i)
            a[j] = 1;
    }
    
    while(scanf("%d", &n)){
        if(n == 0) break;
        flag = 0;
        /*n = a + b를 만족하는 값 찾기*/
        for(int i = 3; i <= n / 2; i++){
            if(a[i] || a[n - i]) continue; //둘 중에 하나가 소수가 아닌 경우
            flag = 1;
            printf("%d = %d + %d\n", n, i, n - i);
            break;
        }
        /*못 찾은 경우*/
        if(flag == 0) printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}

 가장 먼저 에라토스테네스의 채를 통해 소수를 먼저 구하고 시작했습니다.

 

 입력을 받은 후에는 3부터 n / 2까지 루프를 돌며 소수가 아닌 수가 들어오면 바로 루프를 넘겨 소수의 합만 진입할 수 있도록 구현했습니다. 여기서 중요한 부분은 소수합을 찾자마자 break를 통해 루프를 종료해야합니다. b - a값이 가장 큰 것을 출력해야하기 때문입니다.

---