intro : 에라토스테네스의 체 방식으로 문제풀이를 성공했다.

문제

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

입력

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

출력

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

문제 풀이 (252ms)

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int tcValMax = Integer.MIN_VALUE;
        int tcCount = Integer.parseInt(br.readLine());
        int[] tcArray = new int[tcCount];
        for (int i = 0; i < tcArray.length; i++) {
            tcArray[i] = Integer.parseInt(br.readLine());
            if (tcArray[i] > tcValMax) {
                tcValMax = tcArray[i];
            }
        }

        boolean[] isPrime = new boolean[tcValMax + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= isPrime.length; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int tc : tcArray) {
            int count = 0;
            for (int i = 2; i <= tc / 2; i++) {
                if (isPrime[i] && isPrime[tc - i]) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

문제 해석

이 문제는 큰 틀의 관점에서 보았을때 2가지의 단계로 나누어 문제를 접근 할 수 있다.

첫번째 단계

조건에서 주어진 2 < N ≤ 1,000,000 에 해당하는 범위의 값들 중 소수를 판별한다.

두번째 단계

위 첫번째 문제에서 판별한 소수들 중에서 테스트 케이스로 주어진 값의 조합으로 구할 수 있는 경우의 수를 구한다. 예를들어 테스트케이스로 5가 주어졌다면, 소수인 2 + 3 의 조합으로 골드바흐 파티션을 만족하므로 1을 출력한다.

첫번째 단계를 접근하기 위해 에라토스테네스의 체에 대해서 알아야 한다.

에라토스테네스의 체 란 ?

2부터 시작해서 소수를 찾아내고 해당 소수의 배수들을 모두 제외시키는 방식으로 소수를 구한다. 이때, 해당 소수는 제외하지않는다. 이렇게 제외를 시키다보면 남은 숫자들은 전부 소수이다.

위 내용을 다음과 같이 세부 단계를 나누어 설명할 수 있다.

먼저, 2부터 n까지의 모든 수를 소수로 가정하고 배열에 표시한다. 2는 소수이므로, 2의 배수(즉, 4, 6, 8, 10 등)는 소수가 아니므로 false로 표시한다. 그다음, 3은 소수이므로, 3의 배수(즉, 6, 9, 12, 15 등)는 소수가 아니므로 false로 표시한다. 4는 이미 2의 배수로 지워졌기 때문에 건너뛰고, 그다음 5는 소수이므로, 5의 배수(즉, 10, 15, 20, 25 등)는 소수가 아니므로 false로 표시한다. 이 과정이 계속해서 반복된다.

결국 소수가 아닌것들을 제외하는 과정을 로직상으로 구현하는것이 첫번째 문제를 푸는 것의 열쇠가 된다. 위 내용을 담은 코드는 다음과 같다. (주석을 참고하자)

첫번째 단계 코드 주석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력값을 받기위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 테스트 케이스로 입력받는 값들중 가장 큰값을 구하기 위한 기준 값
        int tcValMax = Integer.MIN_VALUE;
        // 테스트 케이스 갯수
        int tcCount = Integer.parseInt(br.readLine());
        // 테스트 케이스의 값을 담을 배열 
        int[] tcArray = new int[tcCount];
        // 테스트 케이스 갯수만큼의 반복문을 실행
        for (int i = 0; i < tcArray.length; i++) {
            tcArray[i] = Integer.parseInt(br.readLine());
            // 테스트 케이스 값들중 가장 큰값을 구하는 로직
            if (tcArray[i] > tcValMax) {
                tcValMax = tcArray[i];
            }
        }

        // 테스트 케이스 중에서 가장 큰값에 대한 배열 
        // +1 을 하는이유는 인덱스는 0부터 시작이기에 
        boolean[] isPrime = new boolean[tcValMax + 1];
        // 초기는 전부 소수라고 가정 하고 시작
        Arrays.fill(isPrime, true);
        // 0과 1은 소수가 아님
        isPrime[0] = false;
        isPrime[1] = false;

        // 2부터 시작해서 i * i 가 배열의 길이보다 작은지 검증 
        // i * i 를 하는 이유는 내부 반복문에서 이미 소수인지 검증한 값을 생략하기 위함
        for (int i = 2; i * i <= isPrime.length; i++) {
            // 만약 소수라면
            if (isPrime[i]) {
                // 해당 소수값은 제외하고 소수값의 배수들을 소수에서 제외함
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // ---------------------------- 이 아래는 차후 설명 ----------------------------

        for (int tc : tcArray) {
            int count = 0;
            for (int i = 2; i <= tc / 2; i++) {
                if (isPrime[i] && isPrime[tc - i]) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

여기까지 이해했다면 isPrime 배열안에 소수들만 true 값을 갖게된다.

이제 두번째 단계인 골드바흐 파티션을 구하기 위해서 다음과 같은 방법을 사용하고자한다. 예제를 통해 이해해보자면, 10을 이루는 소수의 합이 있는가를 검증하고 싶다면 아래와 같이 검증한다.

소수 2 + ? = 10 여기서 ? 값은 8 이다 8은 소수가 아니기에 2와 어떤 소수와 합을 이루어 10을 이루는 골드바흐 파티션은 존재하지 않는다. 3 + ? = 10 ? 값은 7 3과 7은 둘다 소수이기에 골드바흐 파티션을 만족한다. 5 + ? = 10 ? 은 5 이기에 이 또한 골드바흐 파티션을 만족한다. 6 + ? =10 ?는 4 이기에 만족하지 못한다. 7 + ? = 10 ?는 3이기에 소수여서 골드바흐 파티션을 만족하지만 이미 3과7 조합이 나왔기에 중복된걸로 간주된다. 이 과정을 코드로 표현 하자면 다음과 같다. (위 코드와 이어진다.)

두번째 단계 코드 주석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력값을 받기위한 BufferedReader 객체 생성
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 출력하기 위한 BufferedWriter 객체 생성
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 값을 한번에 문자열로 다루기 위한 StringBuilder 객체 생성
        StringBuilder sb = new StringBuilder();

        // 테스트 케이스로 입력받는 값들중 가장 큰값을 구하기 위한 기준 값
        int tcValMax = Integer.MIN_VALUE;
        // 테스트 케이스 갯수
        int tcCount = Integer.parseInt(br.readLine());
        // 테스트 케이스의 값을 담을 배열 
        int[] tcArray = new int[tcCount];
        // 테스트 케이스 갯수만큼의 반복문을 실행
        for (int i = 0; i < tcArray.length; i++) {
            tcArray[i] = Integer.parseInt(br.readLine());
            // 테스트 케이스 값들중 가장 큰값을 구하는 로직
            if (tcArray[i] > tcValMax) {
                tcValMax = tcArray[i];
            }
        }

        // 테스트 케이스 중에서 가장 큰값에 대한 배열 
        // +1 을 하는이유는 인덱스는 0부터 시작이기에 
        boolean[] isPrime = new boolean[tcValMax + 1];
        // 초기는 전부 소수라고 가정 하고 시작
        Arrays.fill(isPrime, true);
        // 0과 1은 소수가 아님
        isPrime[0] = false;
        isPrime[1] = false;

        // 2부터 시작해서 i * i 가 배열의 길이보다 작은지 검증 
        // i * i 를 하는 이유는 내부 반복문에서 이미 소수인지 검증한 값을 생략하기 위함
        for (int i = 2; i * i <= isPrime.length; i++) {
            // 만약 소수라면
            if (isPrime[i]) {
                // 해당 소수값은 제외하고 소수값의 배수들을 소수에서 제외함
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // ------------ 여기까지가 위 코드내용과 같고 아래가 골드바흐파티션을 검증하는 로직이다 -------
        
        // 테스트 케이스의 값을 순차적으로 꺼낸다
        for (int tc : tcArray) {
          // 초기 카운트 값 0으로 초기화
            int count = 0;
            // 소수의 합으로 tc를 이룰수 있는지 검증
            // 소수의 합을 구해야 하기 떄문에 2부터 시작
            // tc / 2를 하는 이유는 중복된 조합을 생략하기 위함에 있다.
            for (int i = 2; i <= tc / 2; i++) {
                // isPrime의 index는 각 숫자를 뜻하며 해당 index의 value 값은 소수여부 판별값이다.
                // 결국 tc가 10이이고 i가 3이라면 
                // isPrime[3] = true, isPrime[10 - 3] = true (7은 소수이다.) 
                if (isPrime[i] && isPrime[tc - i]) {
                    // 값 증가
                    count++;
                }
            }
            sb.append(count).append("\n");
        }

        // 출력
        bw.write(sb.toString());
        bw.flush();
        // 객체 자원 반환
        bw.close();
        br.close();
    }
}

I am visible

contact

문제

입력

출력