[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."을 출력한다.

 

요약하면 합하면 제시되는 숫자 N을 만들 수 있는 소수이자 홀수 인 두 숫자를 구하는 문제이다.

테스트 케이스에 따라서 풀이 시간이 상당히 소요되는 문제이기 때문에 유의하여야 한다.

Scanner를 이용한 방식으로 풀면 시간 초과로 인한 에러가 발생한다.

import java.util.Scanner;

public class Goldbach {
    private static final int SIZE = 1000000;
    private static final boolean[] numbersCheck = new boolean[SIZE + 1];
    public static void main(String[] args) {
        int count = 100000;
        Scanner sc = new Scanner(System.in);
        int checkNum;

        checkPrimeNumber();

        for(int i = 0 ; i < count; i++){
            checkNum = sc.nextInt();

            if(checkNum == 0)
                break;

            int mid = checkNum >>> 1;
            for(int num1 = 0, num2 = checkNum; i < mid; num1++, num2--){

                boolean isOddNumber1 = num1 % 2 == 1;
                boolean isOddNumber2 = num2 % 2 == 1;

                boolean isPrimeNumber1 = !numbersCheck[num1];
                boolean isPrimeNumber2 = !numbersCheck[num2];

                if(isOddNumber1 && isOddNumber2 && isPrimeNumber1 && isPrimeNumber2){
                    System.out.printf("%d = %d + %d\n", checkNum, num1, num2);
                    break;
                }
            }
        }

        sc.close();
    }

    private static void checkPrimeNumber(){
        for(int i = 2; i < SIZE; i++){
            if(!numbersCheck[i]) {
                for (int j = i * 2; j <= SIZE; j += i){
                    numbersCheck[j] = true;
                }
            }
            numbersCheck[0] = true;
            numbersCheck[1] = true;
        }
    }
}​

 

 

속도 향상을 위해 BufferedReader와 StringBuilder를 활용한다.

문제 풀이

1. 우선 범위 내의(1백만) 소수들을 구합니다.

2. BufferdReader를 통해서 값을 입력받습니다.

3. 입력받은 값이 null과 0이 아니면 해당 값을 골드바흐 추측 값인지 검사합니다.

3.1 홀수이자 소수인 첫 수 3 부터 +2해가며 값을 검사한다.

3.2 검사하려는 홀수와 입력받은 값 - 홀수에 해당하는 숫자가 소수이면 출력한다.

3.3 골드바흐의 추측은 10의18승 이하에서는 참이다라는 것이 증명되었기 때문에 .1000000 까지의 값에서 "Goldbach's conjecture is wrong."이 출력될 일이 없다.

 

자바 코드

import java.io.*;

public class Main {
    private static final int SIZE = 1000000;
    private static final boolean[] isPrime = new boolean[SIZE + 1];

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

        // 소수를 미리 판별
        checkPrimeNumber();

        while(true){
            String line = in.readLine();
            if (line == null || line.equals("0")) {
                break;
            }

            int checkNum = Integer.parseInt(line);
            boolean found = false;

            for (int num1 = 3; num1 <= checkNum; num1 += 2) {
                if (isPrime[num1] && isPrime[checkNum - num1]) {
                    // String.format을 사용하지 않고 직접 문자열 연결
                    out.write(checkNum + " = " + num1 + " + " + (checkNum - num1) + "\n");
                    found = true;
                    break;
                }
            }

            if (!found) {
                out.write("Goldbach's conjecture is wrong.\n");
            }
        }

        out.flush();
        out.close();
        in.close();
    }

    private static void checkPrimeNumber() {
        java.util.Arrays.fill(isPrime, true); // 모든 수를 소수로 초기화
        isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

        for(int i = 2; i * i <= SIZE; i++){
            if(isPrime[i]) {
                for (int j = i * i; j <= SIZE; j += i){
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }
    }
}

ㅓ

 

골드바흐 문제를 풀다가 골치아픈 상황이 발생했었다.

같은 문제를 스터디하는 사람과 코드 작성 방식이 다를 뿐 풀이 논리는 같은 상황이었는데 내 코드만 시간 초과가 나는 상황이었다.

 

import java.io.*;
public class GoldbachTest {
    private static final int SIZE = 1000000;
    private static final boolean[] numbersCheck = new boolean[SIZE + 1];
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int checkNum = Integer.parseInt(in.readLine());
        checkPrimeNumber();

        while(checkNum != 0){
            for (int num1 = 3; num1 <= checkNum; num1 += 2) {
                if (!numbersCheck[num1] && !numbersCheck[checkNum - num1]) {
                    out.write(String.format("%d = %d + %d\n", checkNum, num1, checkNum - num1));
                    break;
                }
            }
            checkNum = Integer.parseInt(in.readLine());
        }
        out.close();
        in.close();
    }

    private static void checkPrimeNumber(){
        for(int i = 2; i * i < SIZE; i++){
            if(!numbersCheck[i]) {
                for (int j = i * i; j < SIZE; j += i){
                    numbersCheck[j] = true;
                }
            }
        }
    }
}

 

한 참 시간이 흐른 뒤 정답을 알아낼 수 있었는데 String.format을 사용해서 결과 String을 생성해서였다.

자세한 건 새로운 포스트를 작성하면 되겠지만 무슨 일인지 짧게만 요약하자면 String 형변환이나 +연산 등 String을 사용할 때 StringBuilder나 +연산자 보다 format 메서드의 성능이 월등히 떨어져서 발생한 문제였다.

format 메소드는 다른 방식과 달리 문자열을 한 글자 한 글자 일일이 확인하여 %처리를 해준 뒤에 생성하는 형태라 다른 메소드에 비해 처리 속도가 늦은 것으로 보인다. format를 사용하던 것을 +연산자로 바꾸어주니 바로 통과되었다.