[JAVA] 수학 연습문제 - 백준 6588

골드바흐의 추측 구현하기, 에라토스테네스의 체 사용함

 

에라토스테네스의 체를 사용하여 백만까지의 소수를 구한다.

그리고 2부터 원하는 짝수 사이에서, 합이 원하는 짝수가 되는 두 소수를 구한다.

골드바흐의 추측에서, 같은 수를 두 번 더하는 경우도 허용한다.

 

import java.util.Scanner;
public class BOJ6588 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean[] primeFalse=new boolean[1000001];
        primeFalse[1]=true;

        for(int i=2;i<=1000000;i++){
            if(primeFalse[i]==false){
                for(int j=i*2;j<=1000000;j+=i){
                    primeFalse[j]=true;
                }
            }
        }

        while(true){
            int n=sc.nextInt();
            if(n==0){
                break;
            }
            int i;
            for(i=2;i<n;i++){
                if(primeFalse[i]==false && primeFalse[n-i]==false){
                    System.out.println(n+" = "+i+" + "+(n-i));
                    break;
                }
            }
            if(i==n)
                System.out.println("Goldbach's conjecture is wrong.");
        }
    }
}