4장 수학 - (7) 골드바흐의 추측

1. 골드바흐의 추측

1) 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

2) 위의 문장에 3을 더하면

3) 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.

4) 아직 증명되지 않은 문제 => 추측

5) 10^18 이하에서는 참인 것이 증명됨

-6588번(골드바흐의 추측)

=>10^6 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제

#include <iostream>

using namespace std;

int pn;

int p[1000000];

bool c[1000001];

int main(void) {

int n;

// 2부터 100만 사이의 소수 구하기

for (int i = 2; i <= 1000000; i++) {

if (c[i] == false) {

p[pn++] = i;

for (int j = i + i; j <= 1000000; j += i)

c[j] = true;

}

} // p[0]=2, p[1]=3, p[2]=5, p[3]=7 ...

while (1) {

cin >> n;

if (n == 0)

break;

for (int i = 1; i < pn; i++) {

if (c[n - p[i]] == false) {

cout << n << " = " << p[i] << " + " << n - p[i] << endl;

break;

}

}

}

return 0;

}