[수학] 백준 - 골드바흐의 추측

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

-문제해설

처음에는 n까지 소수를 매번 구한 다음 이중포문으로 일일히 n과 같은 값을 찾아서 출력했지만 시간초과가 나왔다...

 

결국 아래 블로그님의 코드를 참고해서 풀었다.

https://brenden.tistory.com/52

 

먼저 입력값을 받기 전에 미리 1_000_000까지 소수를 에라토스테네스의 체를 이용해서 구해준다.

boolean타입의 sosu배열에 값이 true이면 해당 인덱스는 소수이다.

sosu[2] = true

sosu[3] = true

sosu[4] = false

 

에라토스테네스의 체는 루트( n )까지만 반복하면 되긴 하지만 그냥 1_000_000까지 다 돌렸다.

 

다음으로 입력값 n을 입력받고 sosu[ 3 ] 과 sosu[ n-3 ] 둘 다 소수이면 3과 n-3을 출력한다.

이때 왜 3과 n-3이냐면

 

3 + (n-3) == n 이기 때문이다.

 

예를 들어 n이 20일 경우

3 + (20-3) = 20 이다.

 

마지막으로 어떠한 홀수 소수의 합으로 n이 만들어지지 않는 경우 

"Goldbach's conjecture is wrong." 를 출력하기 위해 ok란 변수를 지정했다.

 

 

 

-자바

package math;

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

public class BJ6588 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//소수구하기 - 에라토스테네스의 체 이용
		boolean[] sosu = new boolean[1_000_001];
		for( int i=2; i<=1_000_000; i++ ) sosu[i] = true;
		
		for( int i=2; i<=1_000_000; i++ ) {
			for( int j=i*2; j<=1_000_000; j += i ) {
				if( !sosu[j] ) continue;
				sosu[j] = false;
			}
		}
		
		while( true ) {
			int n = Integer.parseInt( br.readLine() );
			if( n == 0 ) break;
			
			boolean ok = false;
			for( int i=2; i<=n/2; i++ ) {
				if( sosu[i] && sosu[n-i] ) {
					System.out.println( n + " = " + i + " + " + (n-i) );
					ok = true;
					break;
				}
			}
			
			if( !ok ) System.out.println( "Goldbach's conjecture is wrong." );
		}
		
	}
}

 

-파이썬