[백준 알고리즘/BOJ/C++] 골드바흐의 추측

 

 

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있는데 이런 수를 골드바흐의 수라고 한다

 

4 = 2 + 2

6 = 3 + 3

8 = 3 + 5

10 = 5 + 5

12 = 5 + 7

 

이런 식으로 짝수를 두 소수의 합으로 나타내는 표현은 골드바흐의 파티션이라고 하는데,

정수 n이 입력됐을 때 n의 파티션을 출력해야 한다

 

문제는 두 소수의 차이가 최대한 나지 않아야 한다

두 수가 n/2에 최대한 가까워야 한다는 뜻이다

 

따라서 절반으로 쪼개버리면 된다

 

1) 쪼개고

2) 소수인지 확인하고

3) 양쪽에 -1/+1 해주고

4) 소수인지 확인하고

5) 3, 4 반복

 

 

#include <iostream>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t, n, x, y;
    int check = 0;
 
    cin >> t;
 
    for (int i = 0; i < t; i++) {
        cin >> n;
 
        //절반나눈게 소수면 바로 출력
        for (int i = 2; i < (n / 2); i++) {
            if ((n / 2) % i == 0) {
                check++;
                break;
            }
        }
 
        if (check == 0) {
            cout << (n / 2) << " " << (n / 2) << "\n";
            continue;
        }
        
        check = 0;
        
        //절반 나눈게 소수가 아니라면 -1, +1씩 움직여서 소수인지 확인
        x = (n / 2);
        y = (n / 2);
 
        while (true) {
            x -= 1;
            y += 1;
 
            for (int i = 2; i < x; i++) {
                if (x % i == 0 || y % i == 0) {
                    check++;
                    break;
                }
            }
 
            if (check == 0) {
                cout << x << " " << y << "\n";
                break;
            }
 
            check = 0;
        }
    }
}