[백준]6588번 - 골드바흐의 추측(JAVA)

| 문제

 

이 문제를 풀기 위해서는 먼저 소수를 판별하는 알고리즘을 알아야 한다.  소수란 무엇이고 그 알고리즘은 어떤것인지 알아보자.

 

| 소수

: 1과 그 수 자기 자신만을 약수로 갖는 자연수이다. 

 

| 에라토스테네스의 체 

 대량의 소수를 한꺼번에 판별하고 자 할때 사용하는 것이 바로 에라토스테네스의 체이다. 

 소수가 되는 수의 배수를 지우면 남은 수는 소수가 된다'라는 원리로 동작한다.

 

[ 절차 ] 

1. 원하는 숫자까지의 값을 초기화 해준다 (배열에 값 넣기)

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. 

  (자기 자신을 제외한 배수를 지운다)

3. 이미 지워진 숫자의 경우 건너뛰고 진행한다.

 

[ 알고리즘 ]

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 그림의 경우, 11^2>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

---

| 해결 포인트 

1. 테스트 숫자는 1,000,000 을 넘지 않는다.

2. 에라토스테네스의 체를 이용하여 소수를 구한다. 

 

 

import java.util.Scanner;

public class Goldbach_6588 {
	public static final int MAX = 1000000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//2부터 n 까지 n-1개를 저장할 수 있는 배열 할당
		//배열 참조 번호와 소수와 일치하도록 배열의 크기는 n+1길이만큼 할당
		//(인덱스 번호 0 과 1은 사용하지 않음) 
		boolean [] isPrime = new boolean[MAX+1];
		
		//1.초기화 (배열에 2부터 1,000,000 까지 true 값 담아주기)
		for (int i = 2; i <= MAX; i++) {
			isPrime[i] = true;
		}
		//2. i의 배수를 다 false 값으로 바꿔준다 (단, i는 제외하기) 
		for (int i = 2; i <= MAX; i++) {
			for (int j = i*2; j <= MAX; j+=i) {
				if(!isPrime[j]) continue;
				isPrime[j]=false;
			}
		}
		//3. 입력 값 받기
		while(true) {
			int n = sc.nextInt();
			//ok는 두 홀 수 소수의 합으로 n을 나타낼 수 없는 경우를 확인하기 위한 변수 
			boolean ok = false;
			//입력의 마지막줄에 0 하나 주어지면 끝나도록 하기 
			if(n == 0)
				break;
			// 소수 + 소수 이므로  i 와 n-i 둘다 true 이면 소수이다.
			for (int i = 2; i <= n/2; i++) {
				if(isPrime[i] && isPrime[n-i]) {
					System.out.println(n+" = "+i+" + "+(n-i));
					//n을 만들 수 있는 방법이 여러가지라면, b-a가 가장 큰 것을 출력한다. 
					//== a가 가장 작은 수여야 한다. 
					//가장 처음에 나온 i 가 정답이 된다
					//ex) 20 : 3 17 / 7 13 
					ok=true;
					break;
				}
			}
			//두 홀수 소수의 합으로 n을 나타낼 수 없는 경우 
			if(!ok) {
				System.out.println("Goldbach's conjecture is wrong.");
			}
		}
	}
}