[백준 6588] 골드바흐의 추측 (C#, C++) - soo:bak

문제 링크

6588번 - 골드바흐의 추측

설명

백만 이하의 모든 짝수를 두 개의 홀수 소수의 합으로 표현할 수 있는지를 검증하는 문제입니다.

입력으로 하나씩 주어지는 짝수 n에 대해,

n = a + b 형태를 만족하는 두 홀수 소수 a, b를 찾아 출력해야 합니다.

여러 쌍이 존재하는 경우에는 두 수의 차이(b - a)가 가장 큰 것을 선택합니다.

접근법

먼저 빠르게 소수 여부를 판별하기 위해 에라토스테네스의 체를 구성합니다.

참고 : 에라토스테네스의 체 (Sieve of Eratosthenes) - soo:bak

이후 입력으로 주어지는 짝수 n에 대하여:

• 2부터 n / 2 까지의 수 중 하나를 고릅니다.
• 이 수를 s 라고 할 때 n - s 또한 소수인 경우가 있는지 확인합니다.

가장 먼저 조건을 만족하는 쌍 (s, n - s)가 발견되면 즉시 출력하며,

모든 경우를 확인했음에도 불구하고 조건을 만족하는 쌍이 존재하지 않으면,

문제에서 지시한 대로 "Goldbach's conjecture is wrong."을 출력합니다.

---

Code

C#

using System;
using System.Text;

class Program {
  const int MAX = 1_000_001;

  static void Main() {
    var sieve = new bool[MAX];
    sieve[0] = sieve[1] = true;

    for (int i = 2; i * i < MAX; i++) {
      if (!sieve[i]) {
        for (int j = i * i; j < MAX; j += i)
          sieve[j] = true;
      }
    }

    var sb = new StringBuilder();
    while (true) {
      var line = Console.ReadLine();
      if (line == null) break;

      int n = int.Parse(line);
      if (n == 0) break;

      bool found = false;
      for (int i = 2; i <= n / 2; i++) {
        if (!sieve[i] && !sieve[n - i]) {
          sb.AppendLine($"{n} = {i} + {n - i}");
          found = true;
          break;
        }
      }

      if (!found) sb.AppendLine("Goldbach's conjecture is wrong.");
    }

    Console.Write(sb.ToString());
  }
}

C++

#include <bits/stdc++.h>
#define MAX 1'000'001

using namespace std;
typedef vector<bool> vb;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vb sieve(MAX, false);
  sieve[0] = sieve[1] = true;
  for (int i = 2; i * i < MAX; i++)
    if (!sieve[i])
      for (int j = i * i; j < MAX; j += i)
        sieve[j] = true;

  while (true) {
    int n; cin >> n;
    if (!n) break;
    for (int s = 2; s <= n / 2; s++)
      if (!sieve[s] && !sieve[n - s]) {
        cout << n << " = " << s << " + " << n - s << "\n";
        break;
      }
  }

  return 0;
}