#17103: 골드바흐 파티션
문제:
- 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
입력:
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
풀이:
- 이 문제를 풀기 위해서는 에라토스테네스의 체의 개념을 이해해야 된다. 에라토스테네스의 체에 관해서는 #1929: 소수 구하기에 자세한 설명이 나와 있으니 모른다면 참고하길 바란다. 간단하게 설명하면 인덱스 값을 배열에 넣으면 해당 인덱스 값이 소수인지 아닌지 알려주는 배열을 만드는 체라고 생각하면 된다.
- 이 문제는 #6588: 골드바흐의 추측 문제와 상당히 비슷하다. 다른점은 이 문제는 소수쌍이 나올 때 마다 소수쌍의 개수를 세어 주는 문제이고 골드바흐의 추측 문제는 제일 처음 나오는 소수쌍을 출력하는 문제였다.
- 우선, 에라토스테네스의 체를 만들어준다. 주의 해야 될 점은 1,000,001까지의 배열을 만들어야 되기 때문에 배열을 함수안에서 선언하지 않는 것이다. 자세한 이유는 #17299: 오등큰수 별표 부분을 보면 상세히 설명이 되어 있다.
- 에라토스테네스의 체를 만든 후에 입력으로 받은 값을 소수의 합으로 몇 쌍 만들 수 있나 세어주워 된다. 그러기 위해서는 에라토스테네스의 체에서 만들 배열을 2부터 입력 값의 반까지 훑어서 훑는 값과 (입력값 - 훑는 값)이 소수인지 확인 해주면 합하여 입력값이 되는 소수를 찾을 수 있다. 입력 값의 반까지만 훑는 이유는 어짜피 (입력값 - 훑는 값)이 나머지 반의 값을 나타내기 때문이다. 마지막으로, counter로 정답을 출력 해준 뒤에는 다음 값에 더해지는 것을 방지하기 위해 0으로 초기화 하는 것을 잊지 말자.
코드:
#include <iostream>
#define MAX 1000001
using namespace std;
//0과 1은 소수가 아니므로 false로 초기화
bool isPrime[MAX] = {false, false};
int main(){
int n, number, counter = 0;
//입력
cin >> n;
//에라토스테네스의 체
//배열값 모두 true로 초기화
for(int i = 2; i < MAX; i++) isPrime[i] = true;
//배수인 경우에 false로 변환
for(int i = 2; i < MAX; i++){
if(isPrime[i] == false) continue;
for(int j = i+i; j < MAX; j+=i) isPrime[j] = false;
}
//합하여 입력한 수가 나오는 소수가 있을 때 마다 카운터를 올린다
for(int i = 0; i < n; i++){
cin >> number;
for(int j = 2; j <= number/2;j++){
if(isPrime[j] && isPrime[number-j]) counter++;
}
//정답 출력
cout << counter << '\n';
counter = 0; //counter 값 초기화
}
}
Leave a comment