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

9020번: 골드바흐의 추측 (acmicpc.net)

9020번: 골드바흐의 추측

n이라는 숫자가 주어졌을 때, 두 수의 합이 n인 두 소수를 구해야하는 데..

ex) 4 = 2+2

6 = 3+3

8 = 3+5

10 = 5+5

12 = 5+7 

14 = 7+7

16 = 5+11

 

짝수, 홀수 나눠서 어렵게 생각했는 데 문제 다시 읽어보니까 짝수 n이더라

 

n이 짝수니까 n을 절반으로 나눠서 하나씩 차이나게 검사를 하면 됨

n/2-i, n/2+i 의 합은 n이니까

 

백준9020번 - 골드바흐의 추측(C++) (tistory.com)

백준9020번 - 골드바흐의 추측(C++)

 

소수 구하기에서와는 다르게 bool형의 vector을 사용했다

1부터 10000까지의 소수를 구해놔야하기 때문에 

arr[0] ~ arr[10000] 이 필요하므로, 범위는 10001로 잡아줬다

 

다음 코드는 에라토스테네스의 채를 vector<bool>로 표현해줬을 때의 코드

이게 더 좋은 코드 같으니까 이걸로 외우기!

    vector<bool> arr(10001, true);
    arr[1] = false; 
    
    for(int i=2; i*i <=10001; i++){
        if(arr[i]==false) continue;
        for(int j = 2*i; j<=10001; j+=i){
            if(arr[j]==false) continue;
            else arr[j] = false;
        }
    }

그렇게 완성된 코드는 

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n;
    
    vector<bool> arr(10001, true);
    arr[1] = false; 
    
    for(int i=2; i*i <=10001; i++){
        if(arr[i]==false) continue;
        for(int j = 2*i; j<=10001; j+=i){
            if(arr[j]==false) continue;
            else arr[j] = false;
        }
    }
    
    for(int i=0; i<n; i++){
        cin >> m;
        
        for(int j=m/2; j>0; j--){
            if(arr[j] && arr[m-j]){
                cout << j << " " << m-j << "\n";
                break;
            }
        }
    }
    return 0;
}