[백준 / BOJ] C++ 1153 네 개의 소수

1153번: 네 개의 소수

 

문제

https://www.acmicpc.net/problem/1153

1153번: 네 개의 소수

 

 

풀이

자연수 N을 입력받고 합이 N이 되는 네 개의 소수를 출력하는 문제다. 골드바흐의 추측을 알면 쉽게 풀 수 있다. 골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 것이다. 따라서 입력받은 수를 짝수로 만들어주면 된다.

 

본격적 설명에 앞서 네 개의 소수로 나타낼 수 없는 경우는 가장 작은 소수인 2를 네 번 더한 8보다 작은 수일 때다. 따라서 N이 8보다 작으면 -1을 출력하고 프로그램을 종료한다.

 

따라서 먼저 8 이상의 N에 대해 N까지 에라토스테네스의 체를 이용해 소수를 판별한다. 8 이상의 모든 수에 대해 짝수로 만들어주기 위해선 N이 짝수이면 2를 두번 ans 배열에 추가하고 N에서 4를 빼주고 N이 홀수이면 2와 3을 ans 배열에 추가하고 N에서 5를 빼준다. 이제 N은 반드시 짝수가 될 것이고 골드바흐의 추측에 따라 가장 작은 소수부터 prime[i]라 할 때 n - prime[i]가 소수이면 두 개의 소수의 합으로 나타낼 수 있으므로 ans 배열에 추가해 주고 for문을 탈출한다. ans 배열에 있는 값을 모두 출력해 주면 정답이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  // 8 미만인 경우 -1 출력
  if (n < 8) {
    cout << -1;
    return 0;
  }
  // 에라토스테네스의 체
  vector<int> sieve(n + 1, 1), prime, ans;
  for (int i = 2; i * i <= n; i++)
    if (sieve[i]) {
      prime.push_back(i);
      for (int j = i * 2; j <= n; j += i)
        sieve[j] = 0;
    }

  if (n % 2) { // 홀수인 경우
    ans.push_back(2);
    ans.push_back(3);
    n -= 5;
  } else { // 홀수인 경우
    ans.push_back(2);
    ans.push_back(2);
    n -= 4;
  }
  for (int i = 0; i < prime.size(); i++)
    if (sieve[n - prime[i]]) { // N - 소수 가 소수인 경우
      ans.push_back(prime[i]);
      ans.push_back(n - prime[i]);
      break;
    }
  for (int i : ans)
    cout << i << ' ';
  return 0;
}