筛法打素数表---zoj_1951
????????? 筛法打素数表是一种高效的打表方法，体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。需要注意的是，选取质数的时候，循环只需到sqrt(n)就可以。
????????? 与之前的简单打表相比，来分析一个两种方法的效率。
????????? 先看一下简单方法，对于每个需要判断的整数i,最多需要做sqrt（i）次求模的操作，因此算法的效率为sqrt(3)+sqrt(4)+sqrt(5)+sqrt(6)+sqrt(7).......+sqrt(N)
????????? 再分析一下筛法,对于sqrt(N)以内的素数i,做N/i次筛选操作，因此我们可以看到次算法的效率为N/2+N/3+N/5+N/7+N/11+.......+N/k(K是小于sqrt(N)的最大素数)
????????? 简单的数值分析计算一下上面的2个级数，可以看到后者明显小于前者
#include<iostream>#include<cmath>#include<cstdio>using namespace std;int const maxm=1000001;int prime[maxm];void sievePrime(){for(int i=0;i<maxm;i++)prime[i]=1;prime[0]=0;prime[1]=0;int max=sqrt(maxm*1.0);for(int i=2;i<=max;i++){if(prime[i])for(int j=i+i;j<maxm;j=j+i){prime[j]=0;}}}int main(){sievePrime();/*for(int i=2;i<=1000;i++){if(prime[i]){cout<<i<<" ";}}*///cout<<endl;int n;while(scanf("%d",&n)!=EOF&&n){for(int i=3;i<maxm;i++){if(i%2!=0){if(prime[i]){if(prime[n-i]){printf("%d = %d + %d\n",n,i,n-i);//cout<<n<<" = "<<i<<" + "<<n-i<<endl;break;}}}}}return 0;}?