LightOJ 1259 Goldbach`s Conjecture

直接打表暴力找就可以，不过有个坑，要用bool数组标记，用int数组标记会超内存。。mle了好多发，看别人博客说要用bool标记才可以，，以后不用int标记了

#include <cstdio> #include <cstring> #include <cmath> const int MAXN=1e7+5; int prime[700000]; bool book[MAXN]; void getPrime() { memset(prime,0,sizeof(prime)); for(int i=2; i<=MAXN; i++) { if(!book[i])prime[++prime[0]]=i; for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++) { book[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { getPrime(); int t,n,res,time = 0; scanf("%d",&t); while(t--) { res = 0; scanf("%d",&n); for(int i = 1; prime[i] <= n/2; ++i) { if(!book[n-prime[i]]) ++res; } printf("Case %d: %d\n",++time,res); } return 0; }