백준 17103 - 골드바흐 파티션

문제 설명 

 

 

=> 골드바흐의 수를 코딩할 줄 알면 풀 수 있는 문제이다. 

=> check[1] = true를 해주지 않으면 틀리는 경우가 발생한다. 

=> 중복을 제거하기 위해 find() 함수 아랫부분에 중복을 제거하였다. 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;

vector<int> prime;
bool check[1000001];
int cnt=0;

void find(int A)
{
    
    int IndexLimit=0;
    while(prime[IndexLimit]<=A)
    {
        ++IndexLimit;
    }
    
    for(int i=0; i<IndexLimit; ++i)
    {
        if(!check[A-prime[i]]) // A - prime[i] == 소수
        {
            cnt++;
        }
    }
    if(!check[A/2])
    {
        cnt=(cnt/2)+1; return; //중복제거
    }
    else{
        cnt=cnt/2;return;
    }
    
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    check[1]=true;
    for(long i=2; i<=1000000; ++i) //eratosthenes
    {
        if(check[i] == false)
        {
            prime.push_back(i);
            for(long long j=i*i; j<=1000000; j+=i)
            {
                check[j]=true;
            }
        }
    }
    
    int N; // testCase number
    cin>>N;
    int tmp;
    while(N>0)
    {
        cin >>tmp;
        find(tmp);
        cout<<cnt<<'\n';
        cnt=0;
        N--;
    }
    return 0;
}