(실버 2) 골드바흐 파티션 (에라토스테네스의 체)

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초

512 MB

24596

9298

7140

35.885%

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

---

내가 작성한 코드:

#include <iostream>

using namespace std;

#define MAX 1000001

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

bool table[MAX];

for (int i = 2; i < MAX; i++){

table[i] = true;

}

for (int i = 2; i * i < MAX; i++) //true값인 값의 제곱이 MAX이하면 굳이 체크할 필요가 없음

{

if (table[i]) { //소수일 경우

for (int j = i * i; j < MAX; j += i){ //true값인 값의 제곱이 MAX이하면 굳이 체크할 필요가 없음, j+=i 는 중복되는 수가 포함되지만 넘어감.

table[j] = false;

}

}

}

int n;

cin >> n;

for (int i = 0; i < n; i++){

int temp;

int count = 0;

cin >> temp;

for (int j = 2; j <= temp/2; ++j){

if (table[j]){

if (table[temp-j]){

count++;

}

}

}

cout << count << "\n";

}

return 0;

}

이번 문제는 한 짝수가 주어졌을 때 그 수를 소수 두개의 덧셈으로 나타낼 수 있는 경우를 출력하는 문제이다.

에라토스테네스의 체 알고리즘을 사용하여 MAX값 전까지 존재하는 모든 소수를 찾아내 table에 표시해주고,

입력값을 table에 표시된 값으로 빼서 그 수가 소수인 경우 count변수를 활용해 체크해줬다.

 

에라토스테네스의 체 알고리즘은 아래와 같다.
 

1.    2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (위는 120까지가 예시)
2.   짝수 중 유일하게 2는 소수이므로 2는 소수로 체크해준다. (빨간색)
3.   2를 제외한 2의 배수를 모두 지워준다.
4.   3은 소수이므로 3은 소수로 체크해준다.(초록색)
5.   3을 제외한 3의 배수를 모두 지워준다.
6.   5는 소수이므로 5는 소수로 체크해준다.(파란색)
7.   5를 제외한 5의 배수를 모두 지워준다.
8.   ... 3~4단계의 과정을 소수를 만날때마다 해주면된다.

 

위 내용은 https://jun-coding.tistory.com/344 에서 가져왔다.

어차피 혼자 공부하는 기록용으로 작성하는 것이니 문제가 되진 않겠지..요..?