[백준(baekjoon) 6588] 소수 구하기

문제

백준 6588

‘4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.’
하나 이상의 테스트 케이스 T가 주어질 때(0이 나오면 끝), 다음과 같은 규칙으로 출력하라

• 답이 존재 : T = a + b출력 (답이 여러개일 경우 b - a가 가장 큰 것)
• 답이 없음 : Goldbach's conjecture is wrong.출력
• 예시
  
  • 8 = 3 + 5
  • 20 = 3 + 17
  • 42 = 5 + 37

해결

알고리즘

소수를 만드는 방식은 에라토스테네스의 체를 이용하였다.

자세한 방법은 에라토스테네스의 체로 소수 구하기 참고!

방법

T = a + b를 만족하는 홀수 소수 a, b는 많을 것이다.
따라서, 가장 큰 b - a를 찾기 위해 조건을 만족하는 가장 큰 b를 찾는 것이 좋겠다.
(작은 a를 기준으로 하지 않은 이유는 b가 소수가 아닐 가능성이 굉장히 높다고 생각했다.)

그렇다면 T보다 작은 홀수 소수를 바로 찾을 수 있는 방법은 없을까?
에라토스테네스의 체를 활용해 소수를 구하면서 소수 이외의 수에 자신보다 작은 홀수 소수를 저장해두었다.

1. 홀수 소수 구하기
   1,000,000이하의 홀수 소수를 에라토스테네스를 활용했다.
   대신 마지막 소수를 저장해두고 소수가 아닌 경우에 마지막 소수를 저장했다.
   하지만, 이 방법의 경우 짝수 2도 체크가 된다. (2의 배수는 지워지므로 2이외의 짝수는 없다)
   따라서, 2와 1을 -1로 지정했다.
2. 정답 찾기
   위에 저장해둔 값을 활용해 b에 가장 큰 홀수 소수를 바로 대입한다.
   그리고 a값을 구해 조건이 맞을 때 까지 반복하여 답을 출력한다.

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = 1000000;
7.        int[] prime = new int[1000001];
8.
9.        // 소수 체크
10.        int i = 1;
11.        int lastPrime = -1;
12.        boolean end = false; // 에라토스테네스의 체의 마지막 조건 확인 용
13.        while (++i <= n) {
14.            if (prime[i] == 0) {
15.                lastPrime = i;
16.                // 마지막 조건을 넘긴 경우 배수 확인 작업을 하지 않는다.
17.                // 굳이 삽입한 이유 : i * i가 long범위를 넘기게 되어 음수가 되어 이상해짐
18.                if (end || i * i > n) { 
19.                    end = true;
20.                    continue;
21.                }
22.                // 배수 지우는 작업
23.                for (int j = i * i; j <= n; j += i) {
24.                    prime[j] = lastPrime;
25.                }
26.            } else
27.                prime[i] = lastPrime;
28.        }
29.        prime[2] = prime[1] = -1;
30.
31.        int input = sc.nextInt();
32.        while (input != 0) {
33.            int b = prime[input]; // input보다 작은 값 중 가장 큰 홀수소수
34.            int a = input - b;
35.            while (b > 0 && prime[a] != 0) { 
36.                b = prime[b - 1];
37.                a = input - b;
38.            }
39.            if (b > 0)
40.                System.out.println(input + " = " + a + " + " + b);
41.            else // b가 0이하가 되면 답이 없다.
42.                System.out.println("Goldbach's conjecture is wrong.");
43.
44.            input = sc.nextInt();
45.        }
46.    }
47.}

결과