C++高效的质数的判断(2种方法)_c++判断质数

前提准备

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

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

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

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

质数的判断（试除法）

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

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

严谨的证明过程如下图：(注释：分别表示向下，向上取整)

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

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，那么： (mod p) ——1

证明如下图所示：

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

                                                                   (mod p)——2

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

                                                                  a与p-1互质

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

561
1105 
1729 
2465
2821
6601 
8911 
10585
15841
29341
41041 
46657
52633
62745
63973 
75361
101101
115921 
126217 
162401
172081
188461
252601
278545
294409
314821
334153
340561
399001
410041
449065
488881
512461

 这种合数称之为卡迈克尔数，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个循环去判断那些卡迈克尔数，结果如下：

 没有问题，但我要循环5次的话，就出现问题了，如图所示：

 有几个数就判断错误了。我们在保证正确率的前提下再提高效率。

---

下一个内容我们要讨论如何在一个区间内把质数都筛选出来，不见不散

C++区间质数的筛选https://blog.csdn.net/way_back/article/details/122787801

End~~~

写作不易，谢谢大家支持