[백준 6588번/JAVA] 골드바흐의 추측 (문제 풀이, 코드)

골드바흐의 추측

[문제]

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

[풀이]

문제를 잘 읽어야 하는 문제.

문제에선 6 이상의 짝수를 주며, 이 수는 두 홀수 소수의 합으로 나타낼 수 있다고 한다.일단 소수를 찾는 알고리즘은 에라토스테네스의 체가 짧게 걸리므로 이것을 이용한다.간단하게 원리를 설명하면, 2의 배수를 모두 거르고, 3의 배수를 모두 거르고.. 이걸 제곱근 까지만 걸러주면 된다.나는 그렇게 걸러낸 소수를 PrimeNum이라는 배열에 저장했다.

그리고 이제 짝수인 수 n가 주어졌을 때, 두 수의 합은 i(소수)와 n-i 번째 수! n-i번째 수가 소수가 아니면 넘어가면 된다.

그리고 값이 나오지 않는다면 꼭 골드바흐가 틀렸다고 출력해주기.

 

[코드]

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

public class Main {
	static boolean PrimeNum[];
	static int MAX = 1000000;
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrimeNum = new boolean[MAX];
		Seek();
		while(true) {
			int N = Integer.parseInt(br.readLine());
			if(N==0) break;
			FindAns(N);
		}
	}
	public static void Seek() {
		for (int i=2; i<MAX; i++) {
			if(!PrimeNum[i])
				for(int j = i*2; j<MAX; j +=i)
					PrimeNum[j] = true;
		}
		for(int i=0; i<MAX; i++)
			PrimeNum[i] = !PrimeNum[i];
	}
	public static void FindAns(int n) {
		/* 정답 a, b */
		int a = 0; int b = 0;
		for(int i=3; i<=n/2; i+=2) {
			if(PrimeNum[i] && PrimeNum[n-i]) {
				a=i; b=n-i; break;
			}
		}
		if(a>0)
			System.out.println(n+ " = " + a + " + " + b);
		else System.out.println("Goldbach's conjecture is wrong.");
	}
}

[난관]

문제를 제대로 읽지 않아 2 번 틀렸따ㅎㅎ..

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

https://github.com/MOBUMIN/BJalgorithm/blob/master/06000-6999/GoldBach_6588.java

MOBUMIN/BJalgorithm