[JAVA] 백준 17103. 골드바흐 파티션

이 글은 읽는데 약 4분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

  • 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

풀이

N의 최대값은 1,000,000이므로 먼저 이만큼의 에라토스테네스의 체를 만든다.

이후 각 테스트 케이스 N에 대하여 두 수의 합이 N이 되는 모든 경우에 대해서(다만 순서가 바뀌는 경우는 고려하지 않음) 두 수가 모두 소수인지 판별한다.

모두 소수이면 골드바흐 파티션이므로 카운터를 1 증가시키고, 이렇게 모두 검사해서 골드바흐 파티션의 개수를 출력한다.

코드

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    
    int[] primes = eratosthenes(1_000_000);
    
    int T = Integer.parseInt(br.readLine());
    for(int i=0; i<T; i++){
        int N = Integer.parseInt(br.readLine());
        
        int A = 0, B = N, cnt = 0;
        for(int j=0; j<=(N/2); j++){
            if(primes[A] != 0 && primes[B] != 0){
                cnt ++;
            }
            
            A++;
            B--;
        }
        
        sb.append(cnt);
        sb.append("\n");
    }
    
    System.out.println(sb.toString());
    br.close();
}

먼저 100만 까지 에라토스테네스의 체를 만든다. 해당 메소드는 직접 구현한 것이며, int 배열로 검사하고자 하는 수를 인덱스로 주면 소수가 아니면 0이 들어있는 배열을 반환한다.

테스트 케이스 N에 대해서 변수 A는 0부터 1씩 커지고, B는 N부터 1씩 작아진다.
(사실 A=2, B=N-2, j=2부터 시작해도된다. 0과 1은 소수가 아니므로)

그렇게 두 수 A와 B의 합은 당연히 N이 될것이고, A와 B가 모두 소수이면 횟수를 하나 올린다.

public static int[] eratosthenes(int N){
    int[] primes = new int[N+1];
    for(int i=2; i<N; i++){
        primes[i] = i;
    }
    
    for(int i=2; i<=Math.sqrt(N); i++){
        if(primes[i] == 0) continue;
        
        for(int j=i*2; j<=N; j+=i){
            primes[j] = 0;
        }
    }
    
    return primes;
}

에라토스테네스의 체를 만드는 메소드는 이렇게 구현했다.

댓글