素数和素数表

(1) 素数定理

x        x 设π(x)为不超过 x 的素数个数，那么π(x)～        （π(x)和 大小相近）。据此可以估计素数个数。 lnx        lnx

第十二单元 数论算法

(2) 判断素数!

需要头文件：<cmath>

bool isprime(int x) {  int n = sqrt(x)+0.5;   // 假如sqrt(9)返回2.999999999，n＝2，结果可就错了。 for (int i=2;i<=n;i++)   if (x%i==0) return false;  return true; }

两个优化：

① 质数除了2都是奇数。所以除了2，只判断奇数因数就可以了。

② file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps20.png先在素数表内找因数，如果质数表内的最大因数仍未达到x，再继续枚举。如果这个数是素数，就加入到素数表中。

(3) 筛法产生素数表!

bool visited[N];     // 如果被筛，设为true int primes[N], n=0;    // 素数表 memset(visited,0,sizeof(visited)); for (i=2;i<N;i++)  if (!visited) {   primes[n++]=i;   for (j=i+i;j<N;j+=i) visited[j]=true; }

这种筛法虽然有点“朴素”，但是已经够用了。