[JAVA] 백준 수학 연습문제 - BOJ 17103

BOJ17103.java-주어진 수의 골드바흐파티션 갯수 구하기

 

최대입력정수 1,000,000까지의 소수정보를 담은 check[]를 먼저 생성.

인덱스가 false이면 인덱스의 수가 소수, true이면 소수가 아닌 수이다.

골드바흐파티션에서 순서가 바뀐 한 쌍은 하나로 세기 때문에, 주어진 수의 절반까지만 반복문을 적용한다.

2부터 주어진 수의 절반까지 1씩 증가하며, 해당 수와 (주어진 수 - 해당 수)가 소수인지 확인한다.

해당 수와 (주어진 수 - 해당 수)가 모두 소수이면 골드바흐파티션이므로, 카운트를 증가시킨다.

import java.util.Scanner;
public class BOJ17103 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        boolean[] check=new boolean[1000001];
        check[1]=true;

        for(int i=2;i<=1000000;i++){
            if(check[i]==false){
                for(int j=i*2;j<=1000000;j+=i){
                    check[j]=true;
                }
            }
        }

        while(t-->0){
            int num=sc.nextInt();
            int cnt=0;

            for(int i=2;i<=num/2;i++){
                if(check[i]==false && check[num-i]==false){
                    cnt++;
                }
            }

            System.out.println(cnt);
        }
    }
}