문제
6 이상의 짝수 n이 주어졌을 때, 두 홀수 소수의 합으로 나타내라. 여러 답이 있으면 두 소수의 차이가 가장 큰 것을 출력한다. 0이 입력되면 종료한다.
입력
한 줄에 하나씩 짝수 n이 주어진다 (6 이상 1,000,000 이하). 0이면 종료.
출력
각 n에 대해 n = a + b 형태로 출력한다 (a 이하 b, 차이 최대). 불가능하면 Goldbach's conjecture is wrong.을 출력한다.
예제
| 입력 | 출력 |
|---|---|
8 20 42 0 | 8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 |
풀이
에라토스테네스의 체로 소수를 전처리한 뒤, 가장 작은 홀수 소수부터 탐색한다.
- 1,000,000까지 에라토스테네스의 체로 소수 판별 배열을 만든다
- 각 입력 n에 대해 홀수 소수 i = 3부터 순회한다
- i가 소수이면
n - i도 홀수 소수인지 확인한다 - 조건을 만족하는 첫 번째 쌍이 a가 가장 작은 (= 차이가 가장 큰) 답이다
- 결과를
StringBuilder에 누적하여 한 번에 출력한다
핵심 아이디어: 작은 소수부터 순회하므로 처음 찾은 쌍이 자동으로 두 소수의 차이가 최대인 답이 된다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Day305BOJ6588골드바흐추측 { // g
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean[] prime = new boolean[1000001];
for (int i = 2; i * i <= 1000000; i++) {
if (!prime[i]) {
for (int j = i * i; j <= 1000000; j += i) {
prime[j] = true;
}
}
}
StringBuilder answer = new StringBuilder();
while (true) {
int n = Integer.parseInt(br.readLine());
if (n == 0) {
break;
}
StringBuilder sb = new StringBuilder();
for (int i = 3; i <= n; i += 2) {
if (!prime[i]) {
for (int j = n; j > 0; j--) {
if (i + j < n) {
break;
}
if (!prime[j] && j % 2 == 1 && i + j == n) {
sb.append(n).append(" = ").append(i).append(" + ").append(j);
break;
}
}
}
if (sb.length() != 0) {
break;
}
}
answer.append(sb.length() == 0 ? "Goldbach's conjecture is wrong." : sb).append("\n");
}
System.out.print(answer);
}
}복잡도
- 시간: O(N log log N + T * N) - 체 구성 + 쿼리당 소수 쌍 탐색
- 공간: O(N) - 소수 판별 배열