[백준] 17103번 골드바흐 파티션 - Java, 자바

난이도

실버 2

문제

https://www.acmicpc.net/problem/17103

코드

package 알고리즘기초1.b_수학1_연습;

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

// 17103번 골드바흐 파티션
public class boj_6_17103 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        // 소수 구하기 = 소수 false
        boolean[] num = new boolean[1000001];
        num[0] = num[1] = true;
        for (int i = 2; i * i <= 1000000; i++) {
            if (!num[i]) {
                for (int j = i + i; j <= 1000000; j += i) {
                    num[j] = true;
                }
            }
        }

        while (t-- > 0) {
            int temp = Integer.parseInt(br.readLine());
            int ans = 0;
            for (int j = 2; j <= temp / 2; j++) {
                if (!num[j] && !num[temp - j]) ans++;
            }
            System.out.println(ans);
        }
    }

}

풀이

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

        // 소수 구하기 = 소수 false
        boolean[] num = new boolean[1000001];
        num[0] = num[1] = true;
        for (int i = 2; i * i <= 1000000; i++) {
            if (!num[i]) {
                for (int j = i + i; j <= 1000000; j += i) {
                    num[j] = true;
                }
            }
        }

다음으로 a와 b가 N을 구성하는 소수라면, a를 N/2이하까지만 탐색한다.(절반을 넘어가면 수가 겹치므로)
앞쪽에 있는 소수 그리고 뒤쪽에 있는 소수를 탐색하여 둘다 소수이면=골드바흐이면=N이 소수의 합이면 카운트를 증가시킨다.

        while (t-- > 0) {
            int temp = Integer.parseInt(br.readLine());
            int ans = 0;
            for (int j = 2; j <= temp / 2; j++) {
                if (!num[j] && !num[temp - j]) ans++;
            }
            System.out.println(ans);
        }

참고
https://fl0wering.tistory.com/10
https://binghedev.tistory.com/61