素数，是指因子只包含1和其本身的数，那么，我们怎么大批量的判断素数呢？ **（以下代码均基于打表（1~1e6）的基础上完成）** #### 1.按照定义计算 素数的定义就是一个数的因子只包含1和其本身，那么我们直接就按照定义写： ~~~ # include<stdio.h> ​ # include<string.h> ​ # define maxn 1000000+10 ​ int pri[maxn]; int isprime(int n) { for(int i=2;i<n;i++) if(n%i==0) return 0; return 1; } int main() { pri[1]=0; for(int i=2;i<=maxn;i++){ pri[i]=isprime(i); } return 0; } ~~~ 这是最基础的写法，也是最小白的写法。 这种算法的复杂度为O(n^2),复杂度非常的大，对于1e6的数据范围来说肯定要超时，那么还有没有更优化的算法？答案是肯定的 #### 2.基于定义计算的优化算法 我们对一个合数进行考虑，例如12： 它的因子有1 2 3 4 6 12 ，而且1*12=12 ， 2*6=12 ， 3\*4=12 可见，每一个因子都会有另一个对应的因子，观察可得，它们的分布是平均的，左边的一半对应右边的一半，那么最中间的分界线应该是什么？ √n 。 因此，我们只需要对√n 前面的数字进行判断即可。 ~~~ # include<stdio.h> ​ # include<string.h> ​ # define maxn 1000000+10 ​ int pri[maxn]; int isprime(int n) { for(int i=2;i*i<=n;i++)//只需要将i变成i*i即可 if(n%i==0) return 0; return 1; } int main() { pri[1]=0; for(int i=2;i<maxn;i++){ pri[i]=isprime(i); } return 0; } ~~~ 这种算法的复杂度要比上一种好的多，复杂度为O(n√n),但是对于1e6的数据范围来说还是太大了。有没有再快一点的算法？ #### 3.素数筛选法 素数筛选法的思想为： 从2开始，因为2的倍数一定不是素数，所以先把2的倍数全部删去； 接着找下一个素数3，把3的倍数全部删去； 因为4是2的倍数，已经被删去，所以直接找下一个素数5，把5的倍数全部删去； 接着7的倍数，11的倍数，......直到把1e6范围内的合数全部筛选出去，剩下的即为素数： //以下优化均基于打表的基础上 ~~~ # include<stdio.h> ​ # include<string.h> ​ # define maxn 1000000+10 ​ int vis[maxn]; void isprime() { memset(vis,0,sizeof(vis));//此处vis[i]=1表示不是素数，vis[i]=0表示是素数 vis[1]=1; //由于i*i的数据范围可能会超过int，所以需要用long long表示 for(long long i=2;i*i<=maxn;i++){//此处有优化，因为如果一个合数>sqrt(maxn),那么他必定在前面已经被标记过。 if(!vis[i]){ for(long long j=i*i;j<=maxn;j+=i){//此处也有优化，我们只需要判断从i*i开始判断即可。 vis[j]=1; } } } } int main() { int n; isprime(); return 0; } ~~~ 这种算法的复杂度应该为O(n);，是一种非常快速的判断素数的算法。 上述代码有两处优化，第一处优化的证明如下： **假设 maxn > i > sqrt(maxn)并且为合数，那么，他肯定会有一个因子小于等于sqrt(maxn)，因此，i一定在之前已经被标记过了。** 第二处优化证明为： **假设i>2，那么对于 i \* ( i - 1 )：** **如果 i - 1是素数，那么 i \* ( i - 1 ) 一定在之前已经被标记过；** **否则，如果 i - 1 是合数，那么 i - 1能被分成更小的素数。设其中一个为a，那么 i \* ( i - 1 )= i \* ( i - 1 ) / a \* a 也一定被标记过。** 优化后的算法时间会节省非常多，在平常的算法竞赛中，用上述代码就已经可以解决大部分的涉及素数打表的问题。