[백준] '골드바흐의 추측' - Java

<문제 제시>

<문제설명>
1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 
예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 
하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 
2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 
이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 
그 수의 골드바흐 파티션이라고 한다. 
예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5,
12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 
10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 
만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

골드바흐 수 : 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있음
골드바흐 파티션 : 짝수를 두 소수의 합으로 나타내는 표현

<예시 입출력>

---

<문제 해결 과정>

먼저 '골드바흐의 추측' 이라는 개념에 대해 알아야했다. 

골드바흐의 수 : 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있음

골드바흐 파티션 : 짝수를 두 소수의 합으로 나타내는 표현

소수와 짝수를 활용한 문제라고 할 수 있다.

소수를 구하는 get_prime()함수와 짝수를 구하는 로직을 활용해야했다.

Try 1) 

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



    // 1. 배열에 입력받기
    int[] testcase = new int[T];
    for(int i = 0; i < T; i++) {
        testcase[i] = Integer.parseInt(br.readLine());
    }

    // 2. 소수 검사 로직
    int down = 0;
    int up = 0;
    for(int i = 0; i < testcase.length; i++) {
        int low = testcase[i] / 2;
        int high = testcase[i] / 2;

        // low나 high가 소수일때까지 반복하는 알고리즘, 소수판별되면  break로 빠져나감
        // while문 끝에는 low++, high--; 를 입력해주어야함
        int[] low_prime = get_prime_l(low);
        int[] high_prime = get_prime_h(high);


        System.out.println(testcase[i] + "의 함수 처리 후 작은 소수 = " + Arrays.toString(low_prime));
        System.out.println(testcase[i] + "의 함수 처리 후 큰 소수 = " + Arrays.toString(high_prime));

    }
}

public static int[] get_prime_l(int prime) {

    int count = 0;

    List<Integer> list = new ArrayList<>();

    for(int i = 3; i <= prime; i++) {
        for(int j = 3; j <= i; j++) {
            if(i % j == 0) count++;
        }

        if(count == 1) {
            list.add(i);
        }

        count = 0;
    }

    int[] arr = new int[list.size()];

    for(int i = 0; i < list.size(); i++) {
        arr[i] = list.get(i);
    }

    return arr;
}

public static int[] get_prime_h(int prime) {

    int count = 0;

    List<Integer> list = new ArrayList<>();

    for(int i = prime; i >= 3; i--) {
        for(int j = 3; j <= i; j++) {
            if(i % j == 0) count++;
        }

        if(count == 1) {
            list.add(i);
        }

        count = 0;
    }

    int[] arr = new int[list.size()];

    for(int i = 0; i < list.size(); i++) {
        arr[i] = list.get(i);
    }


    return arr;
}

처음 시도했던 코드이다. get_prime_h 함수 로직에서 소수를 찾는 부분이 잘못되었다.

1. 예외처리) 짝수가 입력되지 않았을 경우 '재입력 로직'
2. 수를 배열로 입력받기
3. 소수를 체크하는 로직

로 코드설계 순서를 생각해보고 작성하였지만, 코드가 비대해지고 비효율적이었다.

---

Answer 1) 

while (T-- > 0) {
    int n = Integer.parseInt(br.readLine());
    int first_partition = n / 2;
    int second_partition = n / 2;

    while (true) {

        // 두 파티션이 모두 소수일 경우
        if (!prime[first_partition] && !prime[second_partition]) {
            System.out.println(first_partition + " " + second_partition);
            break;
        }
        first_partition--;
        second_partition++;
    }
}

 

while (T-- > 0) 은 T를 줄여가며 0보다 클때까지만 반복하는 것이다. (=테스트케이스가 더 이상 입력되지 않을때까지)

따로 변수를 선언해 while문 안에서 증감값 처리를 할 수고를 덜은 것이다.

주어진 범위는 0~10000까지이므로, boolean값으로 flag를 만들기 위해선 boolean[10001] 크기의 배열 선언이 필요했다.

/*
false : 소수
range : 0 ~ 10000
*/

public static boolean[] prime = new boolean[10001];

전역변수로 선언하여 모든 함수(get_prime, main)안에서도 사용될 수 있도록 한다.

테스트케이스의 수를 입력받기 전 get_prime()을 한 번 호출하여

"에라토스테네스의 체"를 통해 소수가 아닌 부분은 true로 바꿔준다.

---

cf) "에라토스테네스의 체" 는
체로 걸러내듯 소수를 찾는 방법론이다.

1) 임의 범위의 숫자를 쓰고
2) 소수도, 합성수도 아닌 유일한 자연수 1을 제거한 후
3) 2를 제외한 2의 배수를 제거, 3을 제외한 3의 배수를 제거...
4) 4의 배수는 (2의 배수에서 지워졌으므로 해당하지 않는다), 5를 제외한 5의 배수를 제거..
5) 7을 제외한 7의 배수를 제거한다.
6) 8은 2의배수에서 지워졌고, 9는 3의배수에서 지워졌다. 10또한 2의배수에서 지워졌다.
7) 이러한 방법으로 2배수,3배수,... n배수를 지우다보면 남는 것이 그 범위 안의 소수이다.
8) 일일이 지워가는 과정이 오래걸릴 것 같지만, "특정 범위의 모든 소수를 찾아야할때"에는 빠른 방법으로 통한다.

get_prime() 함수에서는

이 방법에서도 모든 범위의 길이를 반복하지않고 Math.sqrt(prime.length)를 통해 제곱근(루트) 횟수만큼만 반복한다.

만약 true이면 그대로 지나치고, 

이중 for문을 통해 i의 제곱을 한 숫자들 (= i의 배수) 또한 true로 바꿔준다. (=소수가 아님)

---

이 문제에서 찾고자 하는 것은 골드바흐의 파티션이 되는 두 소수의 차이가 가장 작은 것을 찾는 것이다.

T가 주어졌을때 두 소수가 T가 되는 것이므로, n / 2을 통해 첫번째 값과 두번째 값을 만들어주어야한다.

!prime[first_partition] && !prime[second_partition]

으로 초기화해준 1~10000범위의 boolean prime 배열에서 false인 값을 찾는다. (소수 확정)

break로 while문을 나간다. 

남은 테스트케이스가 있으면 반복진행한다.

first_partition--; 
second_partition++;

부분은 가장 처음 구한 두 소수의 차이가 가장 작을때이며, 그 이후로 증감값을 통해 구해지는 값은

그 다음으로 두 소수의 차이가 작을때이다. 따라서 조건문에 해당하지 않고 증감값을 통해 업데이트하다가 

조건문에 맞게되면 찾은 그 값이 두 소수의 차이가 가장 작은 값이다.

---

<전체코드>

public class Main {

	/*
	false : 소수
	range : 0 ~ 10000
	*/
	public static boolean[] prime = new boolean[10001];
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		get_prime();
	
		int T = Integer.parseInt(br.readLine());	// 테스트케이스
	
		while (T-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int first_partition = n / 2;
			int second_partition = n / 2;
	
			while (true) {
	        
				// 두 파티션이 모두 소수일 경우
				if (!prime[first_partition] && !prime[second_partition]) {
					System.out.println(first_partition + " " + second_partition);
					break;
				}
				first_partition--;
				second_partition++;
			}
		}
	
	}

	// 에라토스테네스의 체
	public static void get_prime() {
		prime[0] = prime[1] = true;
	
		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i])
				continue;
			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}

}

---

에라토스테네스의 체를 활용하여 골드바흐의 추측문제를 구할 수 있었다.

골드바흐의 추측에서도 골드바흐 파티션 부분을 구하는 부분이 어려웠다.

두 소수를 구하는 것만이 아닌 두 소수가 되는 가능성있는 케이스 중에 가장 차이가 작은 값을 구하는 부분이

가장 오래 시간이 걸린 부분이었다.

 

---

문제링크)
https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측