LightOJ 1259 Goldbach`s Conjecture 水题

<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\n",++cas,ans); } return 0; } View Code

 

LightOJ 1259 Goldbach`s Conjecture 水题

标签：