6588. 골드바흐의 추측
문제
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
입력
입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n < 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이 때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.
예제 입력
8 20 42 0
예제 출력
8 = 3 + 5 20 = 3 + 17 42 = 5 + 37
1. 접근
골드바흐의 추측이란 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표현할 수 있다는 추측이다.
또한 하나의 소수를 반복하여 사용하는 것을 허용한다.
예를 들어, 22는 3+19로, 또는 5+17로도 표현할 수 있다. 10^18 까지 골드바흐의 추측이 참임을 확인했다고 한다.
따라서 모든 소수들의 조합들을 확인하는 과정을 거치고자 한다.
2. 풀이
모든 소수를 빠르게 찾는 방법이 중요할 것이다.
여러 테스트케이스들이 소수인지 판별하는 유명한 소수판별 알고리즘은 에라토스테네스의 체라는 방법이다.
2부터 오름차순으로 모든 수(x)를 확인하는데, x가 체크되어 있지 않다면 소수고, 나머지 x의 배수는 모두 비소수로 체크한다.
코드로 확인해보자.
1 2 3 4 5 6 7 8 9 10 11 12 | #include <stdio.h> using namespace std; int t, n; bool num[1000002]; int main() { for (int i = 2; i <= 10000; ++i) if (num[i] == false) for (int j = 2; i*j <= 1000000; ++j) num[i*j] = true; } | cs |
또한 더욱 최적화가 가능한데, 이는 소수의 성질 상 가능한 부분이다.
12를 생각해보면, 12의 약수는 1, 2, 3, 4, 6, 12 로 여섯개다.
이 때 주목할 점은 12, 6, 4는 앞의 1, 2, 3으로 12를 나눈 뒤의 몫이라는 점이다.
따라서 소수인지를 판별하는 에라토스테너스의 체를 적용할 때, x는 n의 제곱근까지만 확인하면 된다.
문제의 경우 백만 이하의 짝수 중 소수를 찾아야 하기 때문에, x는 10,000까지만 확인해도 된다.
이제 주어진 짝수가 prime 배열의 두 소수의 합으로 표현가능한지 확인해야한다.
표현할 수 있는 방법이 여러가지라면 두 소수의 차이가 가장 큰 케이스를 출력해야 하므로, 가장 작은 소수부터 확인하면 되겠다.
즉, n에 대해 소수 x와, n-x 둘 다 존재하는지 가장 작은 x부터 확인하는 것이다.
또한 짝수를 두 소수의 합으로 표현하는데 주목할 점은, 주로 작은 소수의 합과 큰 소수의 합으로 표현된다는 점이다.
예를 들어 40까지의 짝수를 보면
주로 3, 5, 7 등의 작은 소수가 항상 등장한다는 것을 알 수 있다. (2는 짝수이기 때문에 당연히 등장하지 않는다)
따라서 소수들을 따로 모아두기 보다, 모든 수에 대해 소수인지 판별하는 배열을 유지하는게 더 이득일 것이다.
작은 소수가 항상 등장하고, n-x를 빠르게 찾는게 관건이라, 소수들을 따로 모아둔다면 탐색은 빠르면 log(N)이지만
모든 수에 대해 판별하는 배열이라면 거의 원타임에 탐색이 해결된다. (해당 인덱스에 가서 확인만 하면 된다)
3. 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include <algorithm> #include <stdio.h> #include <vector> using namespace std; bool prime[1000002]; vector<int> test; int m, sqm, t, i, j; int main(void) { while (1) { scanf("%d", &t); if (t == 0) break; test.push_back(t); m < t ? m = t : 0; } sqm = sqrt(m); for (i = 2; i <= m; ++i) { if (prime[i] == false) for (j = 2; i * j <= m; ++j) prime[i*j] = true; } int s = test.size(); for (i = 0; i < s; ++i) { for (j = test[i] - 3; ; --j) { if (prime[j] == false) { if (prime[test[i] - j] == false) { printf("%d = %d + %d\n", test[i], test[i] - j, j); break; } } } } return 0; } | cs |
4. 후기
골드바흐의 추측에 대해 알고 있는지에 따라 풀 수 있고 없고가 확연히 드러나는 문제가 몇가지 있다.
그러한 문제들을 몇가지 알아보고자 한다.