골-드바흐의 추측

골드바흐의 추측

 

백준 6588번 문제

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

6588번: 골드바흐의 추측

 

 

 

1. 문제

 

 

 

 

2. 풀이

2.1 풀이 방법

에라토스테네스의 체를 사용해서 테스트 케이스의 최대 값(= 100,000)까지 각 숫자가 소수인지 아닌지를 판별한다.

소수로 나누려는 숫자의 절반까지 탐색하면서 해당 숫자를 소수로 뺀 나머지가 소수인지 판별한다.

 

 

 

2.2 코드

2.2.1 makePrimeSet

주어진 size까지의 숫자들이 소수인지 아닌지 판별한다.

 

[makePrimeSet]

public static boolean[] makePrimeSet(int size) {   //아리스토텔레스의 체
    boolean[] prime = new boolean[size + 1];
    prime[0] = true;
    prime[1] = true;

    for (int i = 2; i * i <= size; i++) {
        if (!prime[i]) {   //소수이면
            for (int j = i * i; j <= size; j += i) {   //i * i 부터(i * i이전의 숫자는 이미 다 걸러짐) size까지 i의 배수를 걸러준다.
                if (!prime[j]) {                       //ex) i = 5일 경우 5 * 1, 5 * 2 ... 5 * 4는 다 걸러져서 판단할 필요없음
                    prime[j] = true;
                }
            }
        }
    }

    return prime;
}

 

중요한건 이 문제에서는 각 숫자가 소수인지 아닌지만 알면 된다는 것이다.

때문에 boolean 배열을 이용해서 각 인덱스로 숫자를 나타내고 해당 숫자가 소수이면 false를 넣어서 판단한다.

 

2부터 시작해서 소수인 숫자들의 배수를 전부 true로 만들어 준다.

이 방식의 장점은 2부터 소수인 숫자들의 배수를 지워나가기 때문에 각 숫자가 소수인지 따로 판별하지 않아도 된다는 것이다.

해당 숫자가 탐색될 때까지 걸러지지 않았다면 그 수는 소수이기 때문이다(나눠지는 수가 없다는 뜻).

 

 

 

 

2.2.2 main

[main]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    boolean[] prime = makePrimeSet(1000000);

    int number;
    while ((number = Integer.parseInt(br.readLine())) != 0){
        boolean flag = false;
        for (int i = 0; i * 2 <= number; i++) {   //합으로 나타내려는 수 number의 절반까지 탐색
            if (prime[i]) {   //소수가 아니라면 넘어간다.
                continue;
            }

            int tempNumber = number - i;
            if (!prime[tempNumber]) {   //number에서 소수 i를 빼준 값도 소수라면 결과식을 생성한다.
                bw.write(String.format("%d = %d + %d\n", number, i, tempNumber));
                flag = true;
                break;
            }
        }
        if (!flag) {
            bw.write("Goldbach's conjecture is wrong.\n");
        }
    }

    bw.flush();
}

 

문제 조건에 의해 0을 입력받으면 반복문을 종료하고 결과를 출력하도록 설정하였다.