백준 17103 자바 - 골드바흐 파티션

문제

---

 

 

문제해결

---

- 에라토스테네스의 체로 입력 조건인 1,000,000까지의 소수를 구한다

- 입력받은 T번만큼 N/2씩 반복문을 돌면서 해당 숫자가 소수면서 N에서 소수를 뺀 값이 소수면 count를 1씩 증가시키면 된다

import java.util.Scanner;

public class B17103 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        boolean[] sosu = new boolean[1000001];
        sosu[0] = true;
        sosu[1] = true;
        for (int i = 2; i <= Math.sqrt(1000000); i++) {
            if (sosu[i]) continue;
            for (int j = i*i; j < 1000001; j+=i) {
                sosu[j] = true;
            }
        }

        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            int tmp = sc.nextInt();
            for (int j = 2; j <= tmp/2; j++) {
                if (!sosu[j] && !sosu[tmp-j])
                    cnt++;
            }
            System.out.println(cnt);
        }
    }
}