[백준/6588] 골드바흐의 추측 - JAVA

📌 문제

알고리즘 분류 : 수학
난이도 : 실버1
출처 : 백준 - 골드바흐의 추측

🦧 문제 풀이 접근

소수의 판정 문제이므로 '에라토스테네스의 체'를 사용한다.
소수를 판별 한 후 입력받은 숫자에 대해 3부터 2씩 증가하면서 조건을 확인한다.

💻 code

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean[] arr = new boolean[1_000_000];
        Set<Integer> set = new HashSet<>();
        for(int i=2;i*i<=1_000_000;i++) {
            if(!arr[i]) {
                for(int j=i;j*i<1_000_000;j++) {
                    arr[i*j]=true;
                }
            }
        }
        for(int i=2;i<1_000_000;i++) {
            if(!arr[i])
                set.add(i);
        }
        while (true) {
            int num = Integer.parseInt(br.readLine());
            boolean flag=false;
            if(num==0)
                break;
            for(int i=3;i<=num/2;i+=2) {
                if(set.contains(i) && set.contains(num-i)) {
                    flag = true;
                    sb.append(num).append(" = ").append(i).append(" + ").append(num-i).append("\n");
                    break;
                }
            }
            if(!flag) {
                sb.append("Goldbach's conjecture is wrong.\n");
            }

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

🥇 결과

🎓 느낀점

소수 문제를 풀기 위해서는 에라토스테네스의 체를 무조건 숙지해야 한다.