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

문제

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

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

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

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

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

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

 

 

일단 이 문제는 에라토스테네스의 체를 기반으로 소수판별을 해야되는게 기본인 문제이다 

 

문제의 큰 맥락은

1. 짝수 n에 대해서 홀수 소수인 a와 b의 합 n=a+b로 나타낼수 있다 

2. 만약 n=a+b의 짝이 여러개면 그 중에서 b-a가 가장 큰 것을 출력한다 

3. 만약 n=a+b로 나타낼수 없다면 Goldbach's conjecture is wrong."을 출력한다

4. 입력의 최대 테스트 케이스는 100,000이다 

5. 0이 입력되면 프로그램은 종료된다 

 

 

 

알고리즘 설계

 

1.

일단 에라토스테네스의 체를 사용하여 2부터 n까지 소수판별을 한다 

-> 나는 처음에 입력값을 받을때마다 2부터 입력값까지의 소수판별을 하였는데 이러면 시간초과가 나더라

해결방법으로는 이 문제의 입력값의 최대는 100000이므로 크기가 1000001인 배열을 만들어서 2~100001사이까지의 모든 수를 소수판별한다. 이렇게 한번 해놓으면 그 다음부터 소수판별을 해줄 필요 없다

 

2. (point)

n=a+b로 나타낼때 

for(int i=2;i<=n;i++){

    if(a가 소수일떄)

        if(n-a가 소수일때)

 

}

 

나는 처음에 입력값에 대해서 a+b로 나타내기 위해 a가 소수이고 n-a가 소수이면 n=a+b로 나타낼수 있는거 까지는 알았지만 for문에서 위와 같이 나타냈었는데 

 

for(int i=2;i<=n/2;i++){

     if (a가 소수일때 && n-a가 소수일때])

 

이렇게 if문을 굳이 나눌 필요도 없고 특히 for문을 입력값 n까지 볼필요도 없고 n/2까지만 봐도 n=a+b로 나타낼수 있는지 업는지 알 수 있었다. ->최대한 시간을 줄이고 코드를 간단하게 하는게 아무래도 좋겠지?

 

#여기서 왜 n-a의 소수판별을 하냐고? 

for문을 돌릴때 굳이 b까지 안가더라도 a만 소수이면 바로 n-a의 소수판별을 하면 되기 때문이다  

 

 

여기까지 해결하였는데 코드를 제출하면 계속 틀렸다고 나오길래 뭔가 했더니

출력문에서

8= 3 + 5로 나타내야 되는데

8=3+5로 나타내고 있어서 틀린거였다..

이런거 사소한거 까지 check하는 안목을 기르자 

 

 

 

 

import java.util.*;
public class Main {
    public  static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int max=1000000;
        boolean []number=new boolean[max+1];
        number[0]=false;
        number[1]=false;
        for(int i=2;i<=max;i++) {
            number[i] = true;
        }

        //에라토스테네스의 체로 소수 판별
        for(int i=2;i<=max;i++) {
            if (number[i]) {
                for (int j = i+i; j <= max; j+=i){
                    number[j]=false;
                }
            }
        }

        while(true){
            int input=sc.nextInt();
            boolean ok=false;
            if(input==0)
                break;
            for(int i=2;i<=input/2;i++){
                if (number[i] && number[input-i]) {  //a도 소수고 입력한수 -a도 소수이면
                        System.out.println(input + " = " + i + " + " + (input - i));
                        ok=true;
                        break;                       // 그 수는 소수의 합으로 이루어 진다

                }
            }
            if(!ok){  //소수의 합으로 나타 낼 수 없으면
                System.out.println("Goldbach's conjecture is wrong.");
            }

        }
    }
}