21.03.25 - [BOJ] 6588. 골드바흐의 추측

[suhyunsim]

문제

• 6588

핵심 아이디어

• 에라토스테네스의 체 활용
• 수를 지웠는 지 체크하는 배열 (지웠을 때 true, 아닐 때 false)
• 소수의 목록을 유지하는 리스트
• 추측인데 10^18 까지는 성립한다고 알려졌기 때문에 그 이하 범위(문제에서는 N이 1,000,000이하의 정수)에서는 에라토스테네스의 체로 풀면 된다.

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q6588;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static final int MAX = 1000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean[] check = new boolean[MAX + 1];
        List<Integer> prime = new ArrayList<>();
        check[0] = check[1] = true;
        for (int i = 2; i * i <= MAX; i++) {
            if (check[i] == true) continue;
            prime.add(i);
            for (int j = i + i; j <= MAX; j += i) { //배수 지우기
                check[j] = true;
            }
        }
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            for (int i = 1; i < prime.size(); i++) {
                int p = prime.get(i);
                if (check[n - p] == false) { //소수찾기
                    System.out.println(n + " = " + p + " + " + (n - p));
                    break;
                }
            }
        }
    }
}