筛法打素数表---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;
}