本文共 764 字，大约阅读时间需要 2 分钟。

自从开始做POJ后我对1 million就没有恐惧感了，直接分配个这么大的空间来存储素数表。感觉空间换时间是个主旋律。

素数表的生成用素数筛选法（小学竞赛学到的）很快。方法是从2开始，对每个目前还标记为素数的数（初始情况下每个数都标记为素数），把它的所有倍数都标记为非素数。这些扫描过去后，一直没被标记的（即保持为素数的）就是所有的素数。

之后的事情就比较简单了，对等差序列中的每个数一个个去查预先生成的素数表，一直数到第n个素数输出即可。用时32ms。

代码如下：

#include 
   
    using namespace std;const int MAX = 1000000;bool primes[MAX];int main(){	memset(primes, true, MAX);		primes[1] = false;	for(int i = 2; i < MAX; ++i)	{		if(primes[i])		{			for(int j = 2; i * j < MAX; ++j)			{				primes[i * j] = false;			}		}	}	/*	for(int i = 2; i < 1000; ++i)	{		if(primes[i])			cout<
    <<"\t";	}	cout<
     
      >a0>>d>>n;		if(!a0 && !d && !n)			return 0;		int cnt = 0;		while(true)		{			if(primes[a0])			{					cnt++;				if(cnt == n)				{					break;				}			}			a0 += d;		}		cout<
      
       <
      
     
   

转载地址：http://axxli.baihongyu.com/