수학 / 백준 17103 골드바흐 파티션

 

문제 접근

에라토스테네스의 체 알고리즘으로 소수들을 미리 판별해 놓은 다음

덧셈을 만족하는 소수들이 있으면 카운트를 올리도록 풀이

중복이 있을 수 있으니 주어진 숫자를 2로 나눈 몫까지만 for문을 작성

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class S17103 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        int[] arr = new int[1_000_001];

        for (int i = 2; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int i = 2; i < arr.length; i++) {
            if (arr[i] == 0) {
                continue;
            }
            for (int j = 2 * i; j < arr.length; j += i) {
                arr[j] = 0;
            }
        }

        for (int i = 0; i < T; i++) {
            int num = Integer.parseInt(br.readLine());
            int cnt = 0;

            if (num == 0) {
                break;
            }

            for (int j = 2; j <= num / 2; j++) {
                if (arr[j] != 0 && arr[num - j] != 0) {
                    cnt += 1;
                }
            }

            sb.append(cnt).append("\n");
        }

        System.out.println(sb);
    }
}