poj2262筛子法素数打表

素数打表：

void oddp()
{
	int i,j;
	for(i=0;i<1000000;i++) a[i]=1;
	a[0]=0; a[1]=0;
	for(i=2;i<1000000;i++)
	{
		if(a[i]==1)
		{
			for(j=i*2;j<1000000;j+=i) a[j]=0;
		}
	}
}

结合POJ2262代码：

int main()
{
	int num;
	int i,flag;
	oddp();
	while(scanf("%d",&num)!=EOF&&num!=0)
	{
		for(flag=0,i=2;i<num;i++)
		{
			if(a[i]==1&&a[num-i]==1)
			{
				printf("%d = %d + %d\n",num,i,num-i);
				flag=1;
				break;
			}
		}
		if(flag==0)
			printf("Goldbach's conjecture is wrong.\n");
	}
	return 0;
}

   瓶颈就在这里，之前用的是O(n^2)，这里的时间复杂度O(n)，速度大大提升了，因此不会超时而通过了。

    这到题的收获是，铸聪师兄教会我算时间复杂度，和筛子法求素数打表。在这里感谢师兄不厌其烦地给我分析，讲解，谢谢师兄！