[백준] 9020 : 골드바흐의 추측 JAVA 풀이

1. 에라토스테네스의 체로 n의 범위까지 소수인 값을 찾아놓는다.

2. 테스트의 개수 T를 입력받는다.

3. 2보다 큰 짝수 n을 입력받는다.

4. n을 둘로 나눈 값을 저장한다.

5. n을 둘로 나눈 값들이 소수가 아니면 하나는 1을 더하고 하나는 1을 뺀다.

6. n을 둘로 나눈 값 둘 다 소수가 될 때까지 반복하고, 출력한다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class Main{
    public static boolean primeList[] = new boolean[10001]; // 에라토스테네스의 체로 소수인지 판별할 배열
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // T를 입력받음
        
        is_prime(); // 에라토스테네스의 체
        
        for(int i=0;i<T;i++){
            int n = Integer.parseInt(br.readLine()); // n을 입력받음
            int head = n/2, tail = n/2; // n을 둘로 나눔
            
            while(true){
                // n을 둘로 나눈 값이 둘 다 소수라면 반복문 종료
                if(primeList[head]==false&&primeList[tail]==false) break;
                // 둘 중 하나라도 소수가 아니면 값을 변화시킴
                head--;
                tail++;
            }
            System.out.println(head+" "+tail); // head + tail = n을 만족하는 두 소수를 출력
        }
    
    }
    // 에라토스테네스의 체 함수
    public static void is_prime(){
        primeList[0] = primeList[1] = true; // 0과 1은 소수가 아니니 true로 변경
        for(int i=2;i<Math.sqrt(primeList.length);i++){ // 2부터 판별할 범위의 제곱근까지
            if(primeList[i]) continue; // 소수가 아니라고 체크한 값은 넘어감
            for(int j=i*i;j<primeList.length;j+=i) primeList[j] = true;
            // 특정 수의 배수라면 소수가 아니므로 true로 변경
        }
    }
}