[백준/C++] 9020번 : 골드바흐의 추측

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한

• 4 ≤ n ≤ 10,000

풀이

이 문제의 핵심은 N/2 - i와 N/2 + i가 둘 다 소수여야 한다는 것이다. (N - i와 i의 관계로도 생각할 수 있다)

 

https://cryptosalamander.tistory.com/30의 풀이에서 배열에 저장하는 부분을 참고했다! 나는 MAX=10000으로 놓고 돌리거나 매 입력마다 for문으로 처리했는데, 아예 처음부터 한 번에 받아서 배열에 넣고 계산하는 방식이 더 깔끔한 것 같다!

#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int T, max=0;
  cin >> T;

  // 한꺼번에 받아서 배열에 저장
  int *num = new int[T]; 
  for (int i = 0; i<T; i++){
    cin >> num[i];
    if (max < num[i])
      max = num[i];
  }

  // 테스트 케이스의 최고 길이까지 bool 배열 생성
  bool isPrime[max+1];
  fill_n(isPrime, max+1, true);
  isPrime[0] = false;
  isPrime[1] = false;

  // 소수 판정
  for (int i=2; i<=sqrt(max); i++){
    if (isPrime[i]){
      for (int j=i*2; j<=max; j+=i)
        isPrime[j] = false;
    }
  }

  // 골드바흐 파티션 출력 -> N/2 + i와 N/2 - i가 모두 소수가 되도록
  for (int i=0; i<T; i++){
    for (int j=num[i]/2; j>0; j--){
      if (isPrime[j] && isPrime[num[i]-j]){
        cout << j << " " << num[i]-j << "\n";
        break;
      }
    }
  }

}

---

N/2까지는 알았으나 거기에서 잘못 접근해서 조금 어려웠던 문제