[백준/c++] 9020번 골드바흐의 추측

mallin·2022년 2월 23일

backjoon

백준

목록 보기

4/13

9020번 문제 링크

문제

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의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

풀이

해당 문제에서는 소수 문제를 풀 수 있는 알고리즘 중 에라토스테네스의 체 를 사용하겠습니다.

총 ✌️가지 방법으로 에라토스테네스의 체를 사용해서 소수를 구해보려고 하는데요.

첫번째, 값을 모두 입력 받은 다음 최고값까지 소수를 확인하는 방법
두번째, 입력받을 수 있는 수가 10,000 까지기 때문에 10,000까지 소수를 확인하는 방법

둘 중 하나의 방법으로 소수를 구한 다음 골드바흐의 파티션을 출력해줍니다.
골드바흐의 파티션을 구하는 방식은

두 값을 더하기 때문에 둘 중 하나의 값은 무조건 num/2 보다 작을 것이다 라는 걸 전제하되,

골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력해야하기 때문에 num/2 부터 시작해서 2까지 반복문을 돌면서 더하는 두 값이 소수인지 찾아줍니다.

소스코드

위 설명처럼 두가지 방법이 있는데 에라토스테네스의 체 알고리즘을 사용하는 방법만 상이하고, 골드바흐의 파티션을 구하는 로직은 동일합니다.

첫번째, 값을 모두 입력 받은 다음 최고값까지 소수를 확인하는 방법

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
    
    int T;     // 테스트 케이스의 개수 
    cin >> T;
    
    int arr[T];       // 입력받은 짝수가 저장되는 배열 
    int max_num = 0;  // 입력받은 짝수 중 가장 큰 수를 저장하는 변수 
    
    for(int i=0;i<T;i++) {
        cin >> arr[i];
        if(max_num < arr[i]) max_num = arr[i];
    }
        
    bool prime_num_arr[max_num+1];			 // 입력받은 수 중 가장 큰 수 까지 소수 여부 저장하는 배열 
    fill_n(prime_num_arr, max_num+1, true);  // 배열은 모두 true 로 초기화 

    prime_num_arr[1] = false;                // 1은 소수가 아니기 때문에 false
    
    for(int i=2;i*i<=max_num;i++) {			 // 2 부터 max_num 의 제곱근까지 돌고, 
        for(int j=i+i;j<=max_num;j+=i) {	 // 해당 값의 배수인 경우 
            prime_num_arr[j] = false;        // 소수가 아니기 때문에 false 
        }
    }
    
    for(int i=0;i<T;i++) {					// 입력 받은 수를 모두 돌면서 
    	
        // 두 값을 더하기 때문에 둘 중 하나의 값은 무조건 num/2 보다 작을 것이다 라는 걸 전제
		// 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력해야하기 때문에 num/2 부터 시작해서 -- 
        for (int j=arr[i]/2;j>=2;j--) { 
            if (prime_num_arr[j] && prime_num_arr[arr[i]-j]) { // 두 값이 모두 소수인 경우 출력
                cout << j << " "<< arr[i]-j << endl;
                break;
            }
        }
    }
  
    return 0;
}

두번째, 입력받을 수 있는 수가 10,000 까지기 때문에 10,000까지 소수를 확인하는 방법

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
    
    int T, num;
    cin >> T;  // 테스트 케이스를 입력 받음 
    
    bool prime_num_arr[10001]; // 입력받을 수 있는 수가 10,000 까지 이기 때문에 
    std::fill_n(prime_num_arr, 10001, true); // 배열 값 true 로 초기화 

    prime_num_arr[1] = false; // 1은 소수가 아니기 때문에 false
    
    for(int i=2; i*i<=10000; i++) { // 10,000 을 돌면서 소수가 아닌 것들을 false 로 바꿔줌 
        for(int j=i+i; j<=10000; j+=i) {
            prime_num_arr[j] = false;
        }
    }

    for(int i=0;i<T;i++) {
        cin >> num; 

        for (int j=num/2; j >= 2; j--) {
            if (prime_num_arr[j] && prime_num_arr[num-j]) {
                cout << j << " "<< num-j << endl;
                break;
            }
        }
    }
        
    return 0;
}