[백준 6588] 골드바흐의 추측

글에 개요

백준 알고리즘 6588번 "골드바흐의 추측" 문제입니다. 에라토스테네스의 체 개념을 알면 쉽게 해결할 수 있습니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

에라토스테네스의 체 (Sieve of Eratosthenes)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

에라토스테네스 체를 활용한 네 번째 문제이므로 참고할 만한 글을 통해 여러 문제를 풀어보시는 것을 추천드립니다.

이 문제의 경우 java로 해결할 때 시간 초과에 대한 이슈가 생길 수 있어 특히 조심하셔야될 것 같습니다.

이 후 이 문제를 통해 확장할 수 있는 문제가 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 6588] 골드바흐의 추측: https://www.acmicpc.net/problem/6588

참고할 글

1. http://brenden.tistory.com/48 ([알고리즘] 에라토스테네스의 체 정리글)
2. http://brenden.tistory.com/49 ([백준 2960] 에라토스테네스의 체)
3. http://brenden.tistory.com/50 ([백준 1978] 소수 찾기)
4. http://brenden.tistory.com/51 ([백준 4948] 베르트랑 공준)

핵심 내용

1. 에라토스테네스의 체 개념을 묻는 문제이다.
2. 1000000까지의 모든 소수를 판단할 수 있는 isPrime 배열에 담아줍니다.
3. 숫자의 제곱근까지만 약수의 여부를 검증하면 된다라는 사실을 아는 전제하에 대칭성이라는 성질을 활용해 n/2까지만 검사를 진행했습니다.

해결 방법

1. 소수인지 아닌지 여부를 파악하기 위한 isPrime 배열의 초기화를 진행해 줍니다.
2. line 14, 15 line을 통해 소수 여부를 갱신해 줍니다.
3. ok 변수는 해당하는 소수 조합이 있는 지 여부를 파악해주기 위한 변수입니다.
4. 핵심내용 3번을 바탕으로 25 line ~ 26 line 처럼 코드를 작성을 진행해주면 마무리됩니다.

해결한 코드

백준 참고 내용

골드바흐의 추측 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	7576	2203	1560	28.969%

문제

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."을 출력한다.

예제 입력 1 

8
20
42
0

예제 출력 1 

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37