수학1_17087 번 : 골드바흐 파티션 JAVA

 

에라토스테네스의 체 방식을 이용하여 소수를 구하고자 한다. 먼저 소수가 false인 boolean형 배열을 만든다.

첫번째 입력값은 앞으로 입력될 값의 갯수이다. int형 변수로 받아서 0이 될때까지 돌아가게 while문을 쓴다.

입력값을 num으로 받아 j와 num-j로 나눈다. j와 num-j를 앞에 만든 아레토스테네스 체로 소수인지 판별한다.

두개 모두 소수라면 count 하나 올라간다.

 

import java.io.*

public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] primeCheck = new boolean[1000001]; // boolean형 배열 생성
        primeCheck[0] = primeCheck[1] = true; // 0과 1은 소수가 아니므로 true
        
        for(int i=2;i*i<primeChcek.length;i++){
        	if(!primeCheck[i]){
                for(int j=i+i;j<primeCheck.length;j+=i){ // for문으로 에라토스테네스 체 소수 판별 초기화
                    primeCheck[j] = true;
                }
            }
        }
        
        int t = Integer.parseInt(br.readLine());
        while(t-->0){
        	int num = Integer.parseInt(br.readLine()); // 입력값 받기
            int count = 0;
            for(int i=2;i<num/2;i++){
            	if(!primeCheck[i]&&!primeCheck[num-j]) //입력값 num을 둘로 나눈 j와 입력값 num-j 모두 소수이면 count 올라간다
                	count++;
            }
            System.out.println(count);
        }
    }
}

 

입력값 비교하는 for문에서 num값을 2로 나눈 값까지 설정한 것은 소수 판별이 겹치는 것을 막기 위함이다.

8 = 3 + 5

8 = 5 + 3 

이렇게 겹치게 되어 count는 두번 올라가게 된다.