[백준(BOJ)]골드바흐의 추측(에라토스테네스의 체) C++

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

9020번: 골드바흐의 추측

 

 

어떤 문제인가?

골드바흐라는 분께서 추측하신 정수론의 미해결 문제를 구현하는 문제이다.

다만, 입력된 n에 대한 골드바흐 파티션이 여러 개일 경우 두 소수의 차이가 가장 작은 것을 출력해야 한다.

 

접근 방법

이 문제에서도 에라토스테네스의 체가 사용된다.

잘 모른다면 에라토스테네스의 체에 대한 이해를 하고 이 글을 보는 것을 추천한다.

 

bool arr[10000 + 1];

for (int i = 2; i <= 10000; i++) {
    arr[i] = true;
}

for (int i = 2; i * i <= 10000; i++) {
    if (!arr[i]) {
        continue;
    }

    for (int j = i * i; j <= 10000; j += i) {
        arr[j] = false;
    }
}

에라토스테네스의 체를 구현한 부분이다.

n이 10,000까지 입력될 수 있으니 10001 크기의 배열을 선언해준다.

그 외의 부분은 에라토스테네스의 체에 대한 이해가 있으면 쉽게 이해할 수 있으니 따로 설명하지 않겠다.

 

int n;
cin >> n;
while (n--) {
    int a;
    cin >> a;

    for(int i=a/2; i >=2;i--){
        if(arr[i]&& arr[a-i]){
            cout << i << " " << a-i << "\n";
            break;
        }
    }
}

n을 입력받고 n번만큼 반복문을 돈다.

각 반복마다 숫자를 입력받고 그 숫자에 대한 골드바흐 파티션을 출력한다.

 

 

a/2 + i와 a/2-i의 합이 a가 되는 특징과 두 소수의 차이가 가장 작은 골드바흐 파티션을 출력해야 하기 때문에 a/2부터 확인해나간다.

for문의 범위와 if문의 조건을 설명했다.

if문의 조건이 참이라면(모두 소수이면서 더했을 때 a인 두 수) 출력해주고 탈출한다.

탈출하는 이유는 다른 골드바흐 파티션이 존재할 수도 있기 때문이다.

 

 

무엇이 어려웠는가?

a/2 + i와 a/2-i의 합이 a가 되는 특징을 알아내는 것이 어려웠고 시간이 오래 걸렸다.

수학 문제들은 구현이 어려운 게 아니라 수학적인 사고를 하는 것이 너무 어렵다.

 

 

배운 점

선배님께서 정수론을 배우지 않았으면 수학 파트 문제들은 힘들 수도 있을 거라 하셨는데 맞는 말씀인 것 같다.

아니 맞아야 된다.....

 

수학은 대단하다.... 나는 멍청하고......