素数-埃氏筛

1742年哥德巴赫在教学中发现每个不小于6的偶数都是两个素数只能被1和它本身整除的数之和。如63314311等等。公元1742年6月7日哥德巴赫写信给当时的大数学家欧拉欧拉在6月30日给他的回信中说他相信这个猜想是正确的但他不能证明。叙述如此简单的问题连欧拉这样首屈一指的数学家都不能证明这个猜想便引起了许多数学家的注意。从哥德巴赫提出这个猜想至今许多数学家都不断努力想攻克它但都没有成功。我们不需要你去证明哥德巴赫猜想。如果哥德巴赫猜想是正确的一个不小于6的偶数都是两个素数之和。那么这个偶数能被至少一个素数对表示如14即可以表示为14311也可以表示为1477。不同的偶数对应的素数对的数目是不一样的如偶数6就只能表示为633。对于每个给定的偶数我们希望知道有多少素数对的和等于该偶数。Input有多组测试数据。每组测试数据占一行包含唯一的一个正偶数n.(6 n 1e7,)。 输出以EOF结束。Output对于每个输入的偶数输出一行包含唯一的一个整数表示有多少个素数对的和是输入的偶数。Sample Input6 14Sample Output1 2#include bits/stdc.h using namespace std; const int N1e55; int b[N]; int prime[N],sign0; void su()//打表 { memset(b,1,sizeof(b)); b[0]b[1]0; for(int i2;iN;i) { if(b[i]) { prime[sign]i; for(int j2;i*jN;j) b[i*j]0; } } } int jud(int x) { if(x1||x0) return 0; for(int i1;prime[i]sqrt(x*1.0);i) if(x%prime[i]0) return 0; return 1; } int main() { int n,ans; su(); while(cinn) { ans0; for(int i1;in/2;i) if(jud(i)jud(n-i)) ans; coutansendl; } return 0; }