[BOJ C++] 9020번 골드바흐의 추측

9020번 골드바흐의 추측

골드바흐의 추측이란 '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다'는 것이다. 수학계의 최대 난제 중 하나이며, 아직까지 증명되지는 않았지만 컴퓨터의 발달로 인해 제법 큰 수에 대해서도 골드바흐의 추측이 맞다고 확인되었다.

이 문제에서는 2보다 큰 짝수를 이루는 두 소수, 골드바흐 파티션을 구해야 하며, 골드바흐 파티션이 여러개 존재할 경우 두 소수의 차이가 가장 작은 것을 골라야 한다.

접근법

1. 1 에서 10,000 까지 수 중에서 소수를 구하기 위해 에라토스테네스의 체를 활용했다.
2. int 타입의 변수(m)에 입력된 짝수를 2로 나눈 값을 할당했다.
3. m 보다 큰 수 중 가장 작은 소수를 a 에 할당했다.
4. m 보다 작은 수 중 가장 큰 소수를 b 에 할당 했고, a 와 b 를 더해서 n 이 나오면 반복문을 멈춘다. n 이 아니라면 b 는 b 보다 더 작은 소수를 찾아 다시 a 와 더해서 n 과 비교하는 작업을 반복한다. b 가 2보다 작아지면 b 에는 다시 m 보다 작은 소수가 대입 되며, a 는 a 보다 큰 소수가 대입된다.

코드 자체에는 별 문제가 없고, 정답 처리 됐지만, 4번을 코드로 구현하는 것이 너무 힘들었다. 좀 더 간단한 논리로 정답을 찾을 수 있다면 좋겠다 싶어서 다른 사람의 소스 코드를 살펴봤다. 아래 코드는 다른 사람들의 코드를 보고 다시 구현해 본 것이다.

#include <iostream>
using namespace std;
 
bool arr[10001];
 
int main()
{
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  arr[0] = 1;
  arr[1] = 1;
 
  for (int i = 2; i <= 100; i++) {
    for (int j = i + i; j <= 10000; j += i) {
      if (!arr[j]) arr[j] = 1;
    }
  }
 
  int T;
  cin >> T;
 
  while (T--) {
    int n, m, a, b, i = 0;
    cin >> n;
    m = n / 2;
    while (1) {
      if (!arr[i] && i >= m) break;
      i++;
    }
    if (i == m) {
      cout << i << " " << i << '\n';
      continue;
    }
    a = i;
    b = i - 1;
    while (1) {
      if (!arr[b]) {
        if (a + b == n) break;
        else if (a + b > n) {
          b--;
          while (arr[b]) b--;
        }
        else {
          a++;
          while (arr[a]) a++;
          b = i - 1;
        }
      } else while (arr[b]) b--;
    }
    if (a > b) cout << b << " " << a;
    else cout << a << " " << b;
    cout << '\n';
  }
}

다른 사람들의 접근법

1. 1 에서 10,000 까지 수 중에서 소수를 구하기 위해 에라토스테네스의 체를 활용했다.
2. n 를 2로 나눈 값을 j 에 대입하고, j가 0이 될 때 까지 반복하는 반복문을 만든다.
3. 만약 arr[j]와 arr[n - j] 모두 소수라면 이것이 골드바흐의 추측을 만족하는 답이다.

처음에는 이 논리가 이해가 잘 안됐는데 보다보니 이해가 됐다. j 와 n - j 를 더해야 n 이 된다.

내 접근법 중 4번을 고쳐보면 다음과 같다.

m 보다 큰 수 중 가장 작은 소수를 a 에 할당하고, m 보다 작은 수 중 가장 큰 소수를 b 에 할당 한다. a 와 b 를 더해서 n 이 나오면 반복문을 멈춘다. n 이 아니라면 b 는 1을 빼고, a 는 1을 더한다. a 와 b 중 하나라도 소수가 아니라면 1씩 증감하는 작업을 반복하며, a 와 b 모두 소수라면 출력한다.

#include <iostream>
using namespace std;
 
bool arr[10001];
 
int main()
{
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  arr[0] = 1;
  arr[1] = 1;
 
  for (int i = 2; i <= 100; i++) {
    for (int j = i + i; j <= 10000; j += i) {
      if (!arr[j]) arr[j] = 1;
    }
  }
 
  int T;
  cin >> T;
 
  while (T--) {
    int n;
    cin >> n;
    for (int j = n / 2; j > 0; j--) {
      if (!arr[j] && !arr[n - j]) {
        cout << j << " " << n - j << '\n';
        break;
      }
    }
  }
}