문제 풀이 전 이론 - 1
- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다
- 위의 문장에 3을 더하면
- 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다로 바뀐다.
- 이는 아직 증명되지 않은 문제이기 때문에 "추측"이다.
- 하지만 $10^18$이하에서는 참인 것이 증명되었기 때문에, 알고리즘 문제를 푸는데에는 전혀 문제가 없다.
문제 풀이
- 이 문제는 n의 최악의 경우가 100만이고, 테스트 케이스 문제이기 때문에
- 크기가 100만인 배열을 할당하여 미리 정답을 저장해놓고, 반복문을 통하여 입출력을 해야한다.
- 입력은 짝수를 받으며, 짝수 = 홀수(소수) + 홀수(소수)이므로, 소수들을 미리 배열에 저장해놓는 방법을 사용한다.
- 일단, 에라토스테네스의 체를 이용하여 100만 이하의 모든 소수들을 미리 배열에 할당해 놓을 것이다. 하지만, 100만 이하의 소수들의 개수를 정확하게 모르기 때문에 가변적으로 저장할 수 있도록 ArrayList를 사용한다.
- 반복문을 돌려서 ArrayList에 저장된 소수값을 가져와 a값에 할당한다. ex) 42 = 3 + b
- 그런데 b가 소수가 아니라면 i를 1 증가시켜 반복문을 돌린다. ex) 42 = 5 + b
- b가 소수가 나왔다면 반복문을 멈춘다. ex 42 = 5 + 37
public class Main {
static final int MAX = 1000000;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
ArrayList<Integer> prime = new ArrayList<Integer>(); // 1~100만까지 소수의 개수를 모르니까 가변적으로 / 테스트케이스에 100만이어서 미리 저장해놓음.
boolean[] check = new boolean[MAX+1];
EratosTenes(prime,check);
while(true) {
int n = scan.nextInt();
if(n == 0) break;
for(int i = 1; i <= prime.size(); i++) { // 홀수 + 홀수 = 짝수이어야되니까 i가 1 즉, 3부터 시작
int p = prime.get(i); // 얘는 3부터 시작해서 5 7 11~임 (소수는 2만 짝수임을 참고)
if(check[n - p] == false) {
System.out.println(n + " = " + p + " + " + (n-p));
break;
}
}
}
}
public static void EratosTenes(ArrayList<Integer> prime, boolean[] check) {
check[0] = check[1] = true;
for(int i = 2; i*i <= MAX; i++) {
if(check[i] == true) {
continue;
}
prime.add(i);
for(int j = i+i; j<=MAX; j+=i) { // 2 , 3 본인들은 냅두고 J+=i로 배수만큼 반복 4,6 등은 이미 지워짐 i+i하면 소수인 본인들은 안지워짐.
check[j] = true;
}
}
}
}
출력
문제로부터 얻어간 것
입력 값의 최악의 경우가 매우 큰 숫자이고 테스트 케이스 문제라면, 일단 배열에 저장해놓고 반복하여 입출력하는 방법을 생각해야한다.
이런 경우에는 일단 배열에 모든 소수들을 저장해놓아야 하므로 에라토스테네스의 체가 유용하게 사용된다. 에라토스테네스의 체를 구현했다면 골드바흐의 추측을 증명하는 것 자체는 어렵지 않다.
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[Unity C#] 선택 정렬(수정) (0) | 2021.03.21 |
---|---|
[Unity C#] 거품 정렬 (0) | 2021.03.21 |
[JAVA] 백준 1929 - 소수 찾기2 (에라토스테네스의 체) (0) | 2021.02.24 |
[JAVA] 백준 1978 - 소수 찾기 (0) | 2021.02.24 |
[JAVA] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법) (0) | 2021.02.24 |