LightOJ - 1259 Goldbach`s Conjecture 欧拉筛

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 10000005;
bool is_prime[maxn];
int prime[maxn/10];
void get_prime() {
	memset(prime,0,sizeof(prime));
	memset(is_prime,0,sizeof(is_prime));
	is_prime[0] = 1; is_prime[1] = 1;
	for(int i=2; i<maxn; i++) {
		if(!is_prime[i])prime[++prime[0]] = i;
		for(int j=1; j<=prime[0]&&prime[j]*i<maxn; j++) {
			is_prime[prime[j]*i] = 1;
			if(i%prime[j]==0)break;
		}
	}
}
int main() {
	get_prime();
	int sum =0,t,n,cnt=1;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n); 
		sum = 0;
		for(int j=1;j<=prime[0]&&prime[j]*2<=n;j++){
			if(n-prime[j]>0&&!is_prime[n-prime[j]]){
				sum++;
			}
		}
		printf("Case %d: %d\n",cnt++,sum);
	}
	
		
	return 0;
}