6588_골드바흐의 추측 (JAVA)

6588번: 골드바흐의 추측

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static boolean flag = false;
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        boolean[] sosu = sosulist(1000000);
        
		while(true){
			flag = false;
			int num = Integer.parseInt(br.readLine());
			if(num==0)
				return;

			int temp = 0;
			for(int i=2; i<num; i++){
				if(!sosu[i]){
					temp = i;

					if(!sosu[num-i]){
						System.out.println(num+ " = "+temp+" + "+(num-temp));
						flag = true;
						break;
					}
				}
			}

			if(!flag)
				System.out.println("Goldbach's conjecture is wrong.");
		}
	}

	private static boolean[] sosulist(int num){
		boolean[] check = new boolean[num+1];
		for(int i=2; i*i<=num; i++){
			if(check[i])
				continue;
			for(int j=i+i; j<=num; j+=i){
				check[j] = true;
			}
		}

		return check;
	}
}

 

처음에는 num보다 작은 소수리스트 중에서 2개 뽑아 합이 num인 경우를 찾았다.

시간초과가 났고, 소수리스트를 모두 탐색하며 2개를 뽑는 것을 수정했다.

또 시간초과가 났고! num을 입력받기 전에 미리 num의 최대값으로 소수리스트를 구해놓았더니 통과했다.

 

 

www.acmicpc.net/board/view/44906

** 위 링크는 6588번 FAQ글이다. 시간초과가 났다면 무조건 참고하기!!

 

 

 

 

 

1. 에라토스테네스의 체를 이용하여 num의 최대값인 1000000까지의 소수를 모두 구한다.

   sosu[]=false이면 소수인 것!

 

2. 2~num-1까지 탐색하며 sosu[i]=false인 것을 찾는다 == 소수인 수 찾기

   만약 sosu[i]==false라면, num-i인 값도 소수인지를 확인한다.

 

3. sosu[i] = sosu[num-i] = false 라면, flag=true로 수정한다.

   만약 2번을 모두 끝낸 후에 flag=false라면, num을 두 개의 소수로 나타내지 못한다는 것이다.

  "Goldbach's conjecture is wrong." 메시지를 띄운다.