백준 9020 번 문제 풀이 C++ :골드바흐의 추측

#69. 백준 9020번 문제 풀이: 골드바흐의 추측

1보다 큰 자연수 중 1과 자기자신을 제외한 약수가 없는 자연수를 소수라 한다. 골드바흐의 추측은, 2보다 큰 모든 짝수는 두소수의 합으로 나타낼수 있다는 것이고, 이러한 수를 골드바흐 수라고 한다. 짝수를 두 소수의 합으로 표현할 것을 골드바흐 파티션이라 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11 이다. 2보단 큰 짝수 n 이 주어졌을 때, 골드바흐 파티션을 출력하시오. 골드바흐 파티션이 여러가지 인 경우 두 소수의 차이가 가장 작은 것을 출력. 입력: 첫줄에 테스트 케이스 T, 다음줄 부터 테스트 케이스 짝수 n이 주어진다. (4 ≤ n ≤ 10,000) 출력: 골드바흐 파티션출력. 소수는 작은 것부터 먼저 출력, 공백으로 구분.

입력/출력

--입력--
3
8
10
16
--출력--
3 5
5 5
5 11

문제풀이+해설

소수로 판단하는 루틴은,
 2 부터 자신보다 작은 수로 나누어 떨어지는 수가 있으면 소수가 아니다.
여기서 계산 횟수를 줄이려면, 수의 제곱근 까지만 나누는 과정을 하면 된다.
제곱근까지만 하면 되는 이유는 100의 경우를 보면, 제곱근은 10이다.
10 이상의 수는 10이전에 소수를 찾을 때 계산된 중복 수이기 때문이다. 예를 들어 25는 4x25 로 4에서 이미 확인됨. 

골드바흐 수의 규칙을 보자.
 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5
짝수의 중간값에서 같은 간격으로 떨어진 소수의 덧셈이다.
8의 경우 중간값 3(중간값 4 에서 -1) + 5(중간값 4에서 +1) 이다.
즉 짝수/2 값에서 1이 가감하면서 소수를 찾으면 된다.

code sol.

코드편집/실행

#include <iostream>
#include <cmath> // sqrt 사용을 위해
using namespace std;
// 소수 판별 함수 구현
int sosu(int n) {
  int i, max_n;
  if(n == 1) return 0; // 1은 소수가 아님
  max_n = (int)sqrt(n); // 제급근까지만 나누어지는 수를 체크하면 됨.
  for(i = 2; i <= max_n; i++) {
    if(n % i == 0) return 0; // 나누어 떨어지면 소수가 아님
  }
  return 1; // 나누어 떨어진 수가 없으면 소수
}

int main() {
  int i, N, n, a, b;
  
  cin >> N; // 테스트 케이스 개수를 받음
  for(i = 0; i < N; i++) {
    cin >> n; // 2보다 큰 짝수
    a = b = n / 2; // 주어진 수의 중간값에서 시작
    while(a > 0) { // 중간에서 좌우로 값을 벌려가면서 소수인지 체크한다
      if(sosu(a) && sosu(b)) { // a, b 가 소수 == 골드바흐 수
        cout << a << " " << b << "\n"; // 출력
        break; // 골드바흐 패턴 출력 완료. 루프 끝
      } else { // 소수가 아니면..
        a--; // 값을 1씩 뺌
        b++; // 값을 1씩 증가
      }
    }
  }
  return 0;
}