수학: 백준 6588 자바(Java) 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

풀이:

주어진 짝수를 두 홀수 소수의 합으로 나타내는 문제이다. 

n = a + b 형태로 출력하는데 n을 만드는 방법 중 b - a 가 가장 큰 수를 출력하라 했으므로 n을 1씩 

마이너스해가면서 소수인 경우를 찾고, 소수라면 n - b = a 식을 통해 찾은 a도 소수인지 확인한다.

만족한다면, StringBuilder sb에 추가하고 n = a + b를 만족하는 소수 조합이 없다면 문제에서 제시한 

문자열을 sb에 추가한다.

 

n을 -1 하면서 소수 조합을 찾기 때문에 먼저 찾은 조합이 b - a 가 가장 큰 조합이 된다.

 

2번의 시간 초과가 발생했는데, 소수 찾는 알고리즘을 보다 효율적인 알고리즘으로 바꾸어 해결했다.

모든 수를 확인할 필요는 없기 때문에 해당 숫자의 √N까지만 확인하는 방법이다.

 

정답:

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

public class Main {
    static StringBuilder sb = new StringBuilder();

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

        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }
            goldbach(n);

        }
        System.out.println(sb);

    }

    public static void goldbach(int number) {
        for (int i = number; i > 0; i--) {
            if (isPrime(i) == true) {
                int temp = number - i;

                if (isPrime(temp) == true) {
                    sb.append(number).append(" = ").append(temp).append(" + ").append(i).append('\n');
                    return;
                }

            }
        }
        sb.append("Goldbach's conjecture is wrong.");
        return;
    }

    public static boolean isPrime(int number) {
        if (number < 2)
            return false;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0)
                return false;
        }
        return true;
    }
}