前提准备

在开始质数的讨论之前，我们先预备一下：

质数的定义：若一个正整数除了1和它自身之外不能被任何自然数整除，则该数称为质数，也叫素数。否则为合数。

由定义可知，所有小于等于1的数既不是质数，也不是合数。

质数的分布较为稀疏，对于一个足够大的数S，不超过S的质数大约有 $\frac{N}{InN}$ 个，也就是说每InN个数约有一个质数，这点读者了解即可。

质数的判断（试除法）

对于质数的判断，最简单也最容易想到的方法就是一个一个的筛选，也叫试除法。

如果要判断一个数N，那么我们要对2~N-1的所有数都筛选一遍吗，显然不用。首先肯定的是N-1肯定不能整除N，那么是否能进一步缩小范围。我先给出答案：2~sqrt(N)

严谨的证明过程如下图：(注释： $\left \lfloor \right \rfloor\left \lceil \right \rceil$ 分别表示向下，向上取整)

?那好，利用这个性质，我们就可以写出一下代码：

Code(O(sqrt(N)))

#include<cstdio>
bool isprime(int num){
	if(num==2)
	    return true;
	if(num%2==0 || num<2)
	    return false;
	else{
		for(int i=3;i*i<=num;i+=2){
			if(num%i==0){
				return false;
			}
		}
		return true;
	}
}
int main(){
	int x;
	scanf("%d",&x);
	if(isprime(x)){
		printf("Yes");
	}
	else{
	    printf("No");
	}
	return 0;
}

尽管如此，这个代码还是优化了许多，我们单独考虑2这个情况，然后从3开始只枚举奇数。

难道这就是最快的算法吗？

Miller-Robbin算法

其实还有一个更厉害的算法，名为Miller-Robbin算法,要想学会，我们首先需要理解一个定理：

费马小定理：

? ? ? ? ? ? ? ? ? ? ? ? ?对于一个质数 p,任意一个自然数a，那么：? $a^{p}\equiv a$ (mod p) ——1

证明如下图所示：

?证明完之后，我们可以左右同时除以一个a,变形成：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $a^{p-1}\equiv 1$ (mod p)——2

这个就不一定成立了，可以发现，当a是p-1的倍数时，左式一定是p的倍数，mod一个p就等于0了，不可能等于右边，所以我们必须加上一个条件：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a与p-1互质

好了，这就是费马小定理。值得注意的是，费马小定理是判断素数的必要不充分条件。如果一个数是质数，它必然满足一上的等式。但是，满足上列等式的数，并不一定是质数。如：

?这种合数称之为卡迈克尔数，561是最小的。他们并不满足费马小定理的逆定理！！！可迈克尔数http://oeis.org/A002997

但是，这种事情发生的概率还是比较小的，我们可以随机生成一批数，排除掉能被p-1整除的数，如果它满足费曼小定理的逆定理，那么该数很大程度上可以称之为质数，不确定就多判定几次。我们再配合一个快速幂求出 a^p-1 mod p的值，完美。

快速幂的详解https://blog.csdn.net/way_back/article/details/122760048?spm=1001.2014.3001.5501

Code(O(1))

#include<cstdio>
#include<cstdlib>
int x;
int pow(int a){
	int b=x-1;
	int ans=1;
	while(b>0){
		if(b & 1){
			ans=((ans%x)*(a%x))%x;
		}
		a=a*a%x;
		b>>=1;
	}
	return ans;
}
bool isprime(){
	int loop=10;
	while(loop--){
		int t=rand();
		while(t%x==0){
			t=rand();
		}
		if(pow(t)!=1){
		    return false;
		}
	}
	return true;
}
int main(){
	scanf("%d",&x);
	if(isprime()){
		printf("Yes");
	}
	else{
		printf("No");
	}
	return 0;
}

用10个循环去判断那些卡迈克尔数，结果如下：