<iostream>
#include <ctime>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=1e7+5;
const int INF=0x3f3f3f3f;
int cnt;
bool v[N];
int prime[700000];
void getprime(){
for(int i=2;i*i<=N-5;++i)
if(!v[i])
for(int j=i*i;j<=N-5;j+=i)
v[j]=1;
for(int i=2;i<=N-5;++i)
if(!v[i])prime[++cnt]=i;
}
int main()
{
getprime();
int cas=0,T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int pos=upper_bound(prime+1,prime+1+cnt,n/2)-prime;
int ans=0;
for(int i=1;i<pos;++i){
if(!v[n-prime[i]])++ans;
}
printf("Case %d: %d
",++cas,ans);
}
return 0;
}
View Code
LightOJ 1259 Goldbach`s Conjecture 水题
标签：