Goldbach's Conjecture

题目

T组询问，每组询问是一个偶数n,验证哥德巴赫猜想回答n=a+b且a，b(a<=b)是质数的方案个数.

分析

我们知道1e7之前有不到1e6个质数，所以我们用埃氏筛法预先把质数筛选出来，vis[]保存是否是质数，P[]从小到大保存质数。对于一个n，只需遍历质数表，假如遍历到P[i]，只需看n-P[i]是否大于P[i]，并且n-P[i]是质数，如果n-P[i]<P[i]直接break就行

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 1e7+10;
int P[1000010],tail;
bool vis[maxn];
ll T,N;
void init(){
    vis[1] = false;
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
ll coun(ll x){
    ll cnt = 0;
    for(int i = 0;i<tail;i++){
        if(x-P[i]<P[i]) break;
        if(!vis[x-P[i]]) cnt++;
    }
    return cnt;
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld",&N);
        printf("Case %d: %lld\n",++kase,coun(N));
    }
    return 0;
}