17103) 골드바흐 파티션 - Java

문제 ) https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

 

풀이 )

에스테네스의 체 와 관련된 문제를 다 한번에 푸니까 빠르게 응용도 되고 더 이해가 빨리된다.

가능하다면 이 글을 보시는 분들도 1929 번부터 쭉풀어보길 ... 추천한다!

처음에는 진입조차 어려웠고, 왜 이렇게 풀어야하나 싶었지만 이방법이 가장 쉬운..? 방법인것같은 생각이다.

27번 줄에 for문 조건을 i <= n/2로 했는데, 
primeNum[i] 와 PrimeNum[n-1] 를 둘다 이미 비교하고 있어서 절반을 넘기면 숫자가 겹치므로 반으로 줄였다.

 

코드 )

import java.io.*;
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));
 
        boolean[] primeNum = new boolean[1000001];
 
        for(int i=2; i<Math.sqrt(1000001); i++) { // 2부터 N까지 전부 돌면서 검사
            for(int j=2; i*j<1000001; j++) { // 소수가 아닌 수를 모두 true로 바꾸는 작업
                
                // 이미 검사가 되어 true 값이 들어갔다면 넘어감
                if( primeNum[i*j]) continue;
                
                // 아직 검사가 안된값이라면 true 값을 넣음
                // ex). i=2, j=2 이면 i*j=4 의값이 true가 됨
                primeNum[i*j] = true;
            }
        }
        
        int T = Integer.parseInt(br.readLine());
        while( T-- > 0) {
            
            int n = Integer.parseInt(br.readLine());
            int count = 0;
            for(int i=3; i<=n/2; i++) { // 절반을 넘어가면 수가 겹치므로 n의 반만 확인한다.
                if( !primeNum[i] && !primeNum[n-i])
                    count++;
            }
            bw.write(count + "\n");
        }
        br.close(); bw.flush(); bw.close();
    }
} cs