골드바흐 파티션 백준 17103번

문제

골드바흐 파티션 백준 17103번

리뷰

골드바흐의 추측과 비슷한 문제다.

주의할 점 ! 같은 수 조합이라면 순서가 다르더라도 같은 파티션으로 생각한다는 것이다.

1. 에라토스테네스의 체를 이용하여 소수를 구한다. --> Prime 함수.
2. TC 개수와 정수 N을 입력받는다. 정수 N은 짝수이고, 2 < N ≤ 1,000,00
3. 가장 작은 소수부터 반복을 진행한다.

for(int i = 2; i < N; i++){ // 소수가 현재 입력 수보다 작은 동안.

    if((p[N-i] + p[i]) == N){

        cnt++;

        if(N-i == i){ // 10 = 5+5; 의 경우를 고려. 
            cnt++; 
        }
    }
}

소수끼리의 합으로 N을 표현할 수 있는지 확인한다.

5+5 처럼 같은 소수를 반복사용할 수 있으니까 N-i == i 인 경우에도 cnt 를 증가시킨다.

맞은 코드

#include <iostream>
#include <algorithm> 
#define MAX 1000000
using namespace std;


int TC;
int p[MAX+1];

void Prime(){

    p[0] = p[1] = 0; // 0과 1은 소수가 아니다.  

    for(int i = 2; i <= MAX; i++){ // 자기 자신을 저장 
        p[i] = i;
    } 

    for(int i = 2; i*i <= MAX; i++){ // 소수의 배수들를 0으로 지운다.  

        if(p[i] == i){

            for(int j = i*i; j <= MAX; j += i ){ // i만큼 건너 뛰어서 배수 찾기.
                p[j] = 0; 
            }
        } 
    }
}

int main(void){

    Prime(); // 에라토스테네스의 체 

    cin >> TC;

    while(TC--){

        int N = 0;
        cin >> N;
        int cnt = 0;

        for(int i = 2; i < N; i++){ // 소수가 현재 입력 수보다 작은 동안.

            if((p[N-i] + p[i]) == N){

                cnt++;

                if(N-i == i){ // 10 = 5+5; 의 경우를 고려. 
                    cnt++; 
                }
            }
        }

        printf("%d\n", cnt/2);

    }

    return 0;
}