今天我们来谈一谈素数的判定/筛法。
对于每一个OIer来说，在漫长的练习过程中，素数不可能不在我们的眼中出现，那么判定/筛素数也是每一个OIer应该掌握的操作，那么我们今天来分享几种从暴力到高效的判定法/筛法。
弱智的譬如从1枚举到n或者是枚举的\(\sqrt{n}\)的算法就不讲了。
1.欧拉筛
欧拉筛是最基本的一种线性筛法，预处理完成之后可以O(1)查询，适合于查询次数多，范围不大的情况。
基本思想：每个合数只让其最大因数（或最小质因数）标记。
为了保证这一点，我们开一个prime数组，把检查到的质数按顺序放入。其作用是对于枚举到的数\(i\) ，可依次乘上
prime数组中元素来标记合数；在标记过程中，如果\(prime[j]|i\) ，则停止这轮标记。
预处理部分：
for(int i=2;i<=n;i++)
{
if(!book[i])prime[++ind]=i;
for(int j=1;j<=ind;j++)
{
if(i*prime[j]>n) break;
book[i*prime[j]]=1;
if(!i%prime[j])break;
}
}
预处理完成之后，\(prime[i](i \leq ind)\)表示一个n以内的质数。
注意：最好不要用这里的\(book[i]\)直接判断输出，会惊起WA声一片da！
2.另一种方法
因为不知道叫什么名字所以先这样吧...
这个判定方法有点玄学...给大家推一下。
证明：令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
明显可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里要注意的一点是，在6的倍数相邻两侧并不一定就是质数。
此时判断质数可以以6为单位快进，即将方法（2）循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可。
代码实现也很简单，不过需要注意的是有两种情况需要特判：
1.这个数是1，需要返回false;
2.这个数是2或3，需要返回true;
其他的按照上面的思路打出来就对了，代码如下：
bool isPrime_3(int num)
{
if(num==1)
return 0;
if(num==2||num==3)
return 1;
if(num%6!=1&&num%6!=5)
return 0;
int tmp=sqrt(num);
for(int i=5;i<=tmp;i+=6)
if(num%i==0||num%(i+2)==0)
return 0;
return 1;
}
这种判断的方法的速度应该算是很快了，判断\(40W\)个数是否是素数只需要\(0.099s\)。
3.Miller-Rabin判断法
这个方法骑士我没有过多地进行了解，但是据说它很玄学！
代码也比较复杂
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll qpow(ll x,ll y,ll p)//x^y mod p
{
ll ans=1,m=x;
while(y)
{
if(y&1)ans*=m;
ans%=p;
m*=m;
m%=p;
y>>=1;
}
return ans;
}
bool check(ll x,ll y,ll p)
{
ll q=qpow(x,y,p);
if(q!=1&&q!=p-1)return 0;
if(q==p-1)return 1;
if(q==1&&(y&1))return 1;
return check(x,y>>1,p);
}
bool mil(ll x)
{
if(x<=1)return 0;
if(x==2||x==7||x==61||(check(2,x-1,x)&&check(7,x-1,x)&&check(61,x-1,x)))/*底数RP++*/return true;
return 0;
}
int main()
{
int n,m;
ll k;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>k;
if(mil(k))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
很明显，mil函数中第二个if里面的数字是可以修改的，也决定了你的正确率（最好选择素数）
如果选择\(2,3\)作为这个底，可以通过130w以内的数据，如果用\(2,7,61\)作为底，可以通过4.7亿以内的数据（真的玄学）
当然，如果选其他的质数作为底，错误率也很低，只有\(4^{-k}\)
其他的就不多讲了吧...以后深入了解了之后可能会更新。
ov.