首页 > 代码库 > poj 2262 Goldbach's Conjecture

poj 2262 Goldbach's Conjecture

素数判定...很简单= =.....只是因为训练题有,所以顺便更~

 1 #include<cstdio> 2 #include<memory.h> 3 #define maxn 5000005 4 int prime[maxn]; 5 void f() 6 { 7     memset(prime,0,sizeof(prime)); 8     prime[0] = prime[1] = 0; 9     for(int i = 2; i < maxn; i++)10     {11         if(!prime[i])12         {13             for(int j = 2 * i; j < maxn; j += i)14                 prime[j] = 1;15         }16     }17 }18 int main()19 {20     freopen("input.txt","r",stdin);21     int n,i;22     f();23     while(scanf("%d",&n) && n)24     {25         for(i = 3; i < n /2; i += 2)26         {27             if(!prime[i] && !prime[n - i])28                 break;29         }30         printf("%d = %d + %d\n",n,i,n-i);31     }32     return 0;33 }