문제
자연수 N이 주어질 때, N을 네 개의 소수의 합으로 나타내라. 불가능하면 -1을 출력한다.
입력
첫째 줄에 자연수 N이 주어진다.
출력
네 개의 소수를 공백으로 구분하여 출력한다. 불가능하면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
20 | 2 2 3 13 |
풀이
골드바흐의 추측을 활용하여 N을 작은 소수 2개와 골드바흐 분해 2개로 나눈다.
- 에라토스테네스의 체로 N 이하의 소수를 모두 구한다
- N이 8 미만이면 불가능(-1)이다
- N이 짝수이면 2+2를 빼고 나머지를 두 소수의 합(골드바흐)으로 분해한다
- N이 홀수이면 2+3을 빼고 나머지(짝수)를 두 소수의 합으로 분해한다
- 골드바흐 분해는 소수 리스트를 순회하며 두 소수의 합이 목표와 같은 쌍을 찾는다
핵심 아이디어: 4 이상의 짝수는 두 소수의 합(골드바흐의 추측)으로 분해 가능하므로, 짝홀에 따라 2+2 또는 2+3을 먼저 빼면 나머지는 항상 골드바흐 분해가 가능하다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day778BOJ1153네개의소수 {
static int n;
static boolean[] isPrime;
static int[] ans = new int[4];
static List<Integer> prime;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
prime = new ArrayList<>();
artaos();
if (n < 8) {
System.out.println(-1);
return;
} else {
if (n % 2 == 0) {
n -= 4;
goldbach(n);
ans[0] = ans[1] = 2;
} else {
n -= 5;
goldbach(n);
ans[0] = 2;
ans[1] = 3;
}
}
for (int i = 0; i < 4; i++) {
System.out.print(ans[i] + " ");
}
}
static void goldbach(int num) {
for (int i = 0; i < prime.size(); i++) {
for (int j = 0; j < prime.size(); j++) {
int sum = prime.get(i) + prime.get(j);
if (sum == num) {
ans[2] = prime.get(i);
ans[3] = prime.get(j);
return;
} else if (sum > num) {
break;
}
}
}
}
static void artaos() {
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (isPrime[i])
prime.add(i);
}
}
}복잡도
- 시간: O(N log log N)
- 공간: O(N)