(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; } |
这种筛法虽然有点“朴素”,但是已经够用了。
|