1742년, 골드바흐가 오일러에게 보낸 편지 한 통에서 시작되어 280년 넘게 미해결로 남아 있는 추측이다.

\(2\)보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.

\(4 = 2+2\), \(6 = 3+3\), \(8 = 3+5\), \(100 = 3+97\). 컴퓨터로 \(4 \times 10^{18}\) 이하의 모든 짝수에 대해 반례가 없음이 확인되었지만, 모든 짝수에 대한 증명은 아직 존재하지 않는다.

이 문제의 과제는 단순하다. 반례를 하나 제출하라. 즉, 두 소수의 합으로 나타낼 수 없는 짝수 \(E\) (\(4 \le E \le N\))를 한 줄에 출력하면 된다. 채점기는 \(E\) 이하의 소수를 에라토스테네스의 체로 전부 구한 뒤, \(E = p + q\) 분해가 정말로 하나도 존재하지 않는지 정직하게 전수 검증한다. 검증을 통과하는 어떤 \(E\)든 정답이다.

한 가지 미리 알려 둘 사실: 채점기가 제한 시간 안에 검증할 수 있도록 탐색 상한은 \(N = 10^8\)인데, 이 범위는 인류가 이미 반례가 없음을 확인한 \(4 \times 10^{18}\) 안에 완전히 포함된다. 그러므로 이 문제에서 정답을 받는 유일한 방법은 이미 검증된 수학이 틀렸음을 보이는 것뿐이다. 이 사이트의 다른 Master 문제들이 "사실상 불가능"이라면, 이 문제는 증명 가능하게 불가능하다. 그 사실을 알고도 제출 버튼을 누르는 사람을 위한 기념비로서 여기에 세워 둔다.

그럼에도 AC를 받았다면 — 채점 서버에 우주선(cosmic ray)이 스쳤는지 먼저 확인하고, 그다음 필즈상 수상 소감을 준비하라.

\(N = 10^8\).

출력하는 \(E\)는 \(4 \le E \le N\)인 짝수여야 한다. 참고: \(4 \times 10^{18}\) 이하에는 반례가 존재하지 않음이 이미 알려져 있다.

첫째 줄에 탐색 상한 \(N\)이 주어진다.

두 소수의 합으로 나타낼 수 없는 짝수 \(E\) (\(4 \le E \le N\))를 한 줄에 출력한다.

그러한 \(E\)가 실제로 반례라면 (즉, 어떤 소수 \(p\), \(q\)에 대해서도 \(E \ne p + q\)라면) 정답이다.

riseoj 작성

출처 Original