직대딩 블로그

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong." 을 출력하라고 문제에 나와있는데 그럴 필요없다. 왜냐면 문제에서 주어진 n의 범위는 6 ≤ n ≤ 1000000 이고, 골드바흐의 추측은 이미 10의 18제곱 까지 증명되었기 때문이다. ​ 그러므로 그냥 에라토네스의 체를 이용하여 ~n 까지의 소수의 개수를 미리..