백준 17103번: 골드바흐 파티션 (C++)

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

---

Solved By: Primality Test

 

#include <iostream>
#include <cmath>
#include <memory.h>
#define MAX 1000000
using namespace std;

int T;
int n;
bool isPrime[MAX];

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void getPrime(){
    memset(isPrime, true, sizeof(isPrime));
    for(int i = 2; i <= sqrt(MAX); i++){
        if(isPrime[i]){
            for(int j = i + i; j <= MAX; j += i){
                isPrime[j] = false;
            }
        }
    }
    return;
}

int gold(int v){
    //cout << "Value is " << v * 2 << '\n';
    int cnt = 0;
    for(int i = 2; i <= v; i++){
        if(isPrime[i] && isPrime[2 * v - i]){
            //cout << i << ' ' << 2 * v - i << '\n';
            cnt++;
        }
    }
    return cnt;
}

int main(){
    fastIO();
    getPrime();
    cin >> T;
    while(T--){
        cin >> n;
        cout << gold(n / 2) << '\n';
    }
    
    return 0;
}