BOJ) 골드바흐의 추측 (9020 번)

골드바흐의 추측

9020번: 골드바흐의 추측

 

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

이러한 수를 골드바흐 수라고 한다.

 

소수는 에라토네스의 체를 이용하면 수월하게 소수를 구할 수 있다.

에라토네스의 체의 개념을 다시 환기하기 위해 작성한다.

 

추가적으로, 이 문제에서 출력 부분에 String.format을 이용해서 출력하는 방법과 띄워쓰기와 new line을 append 해주며 출력하는 방법을 이용해봤는데, 메모리와 속도 측면에서 append 해주는게 훨씬 효율적이었다.

생각보다 String.format의 퍼포먼스가 좋지 않아서 추가해본다.

 

~> 요약 : 소수는 에라토네스의 체로, String.format < append value

 

코드

 

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

public class GoldBach_9020 {
    final static String SPACE= " ", NEW_LINE = "\n";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()), max =0;
        int[] numArr = new int[n];

        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            numArr[i] = num;
            max = Math.max(max, num);
        }

        br.close();
        solution(numArr, max);
    }

    private static void solution(int[] numArr, int max) {
        boolean[] prime = initPrimeArray(max);
        StringBuilder sb = new StringBuilder();

        for(int num : numArr) {
            int[] goldBach = getGoldBachPartitions(num, prime);
            sb.append(goldBach[0]).append(SPACE).append(goldBach[1]).append(NEW_LINE);
        }
        System.out.println(sb.toString());
    }

    private static int[] getGoldBachPartitions(int num, boolean[] prime) {
        int left = num/2, right = left;
        boolean isGoldBachPartitions = prime[left] && prime[right];

        while(!isGoldBachPartitions) {
            left--;
            right++;
            isGoldBachPartitions = prime[left] && prime[right];
        }

        return new int[] {left, right};
    }

    private static boolean[] initPrimeArray(int n) {
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);

        for(int i=2; i<n; i++) {
            if(prime[i]) {
                for(int j= i*i; j<n; j+=i) {
                    prime[j] = false;
                }
            }
        }

        return prime;
    }
}