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

소수를 구하는 방법은 크게 두가지가 있다.

1. 어떤수 N이 소수인지 판별하는 방법
특정수 N이 소수인지 확인하기 위해 i=2부터 i*i<=N 까지 N이 안나누어 떨어지면 소수임을 확인할 수 있는 방법이다.

방법1

 

2. N까지의 자연수 범위로 소수를 찾는 방법 (에라토스테네스의 체)
2부터 N까지의 수를 배열로 두고, 아직 지워지지 않은 수를 소수로 두고, 그 배수들을 쭉 지우는 과정을 반복하여 소수를 확인하는 방법이다.

방법2

 

위의 문제는 1000000까지의 범위에서 소수를 쭉 구해놓으면 편하게 문제를 풀 수 있으므로 두번째 방법인 에라토스테네스의 체를 이용하는 방법을 사용하였다. prime이라는 배열을 소수를 저장하기 위해 사용하였다. prime[i]=1 이면 소수이고, prime[i]=0 이면 아직 미방문, prime[i]=-1 이면 소수가 아님을 규칙으로 정하고 접근하였다.

package online.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_6588_골드바흐의추측 {
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        
        //에라토스테네스의체
        int[] prime= new int[1000001];
        for(int i=2;i<=1000000;i++) {
            if(prime[i]==0) {
                prime[i]=1;
                for(int j=i*2;j<=1000000;j=j+i)
                    prime[j]=-1;
            }
        }
        
        
        while(true) {
            int num=Integer.parseInt(br.readLine());
            if(num==0) {
                return;
            }
            for(int i=2;i<=num/2;i++) {
                if(prime[i]==1) {
                    int a=i;
                    int b=num-a;
 
                    if(prime[b]==1) {
                        System.out.println(num+" = "+a+ " + " +b);
                        break;
                    }
                }
                
                
            }
            
        }
        
    }
}