如何判断一个数是不是素数/质数——三种方法超详细总结，包含目前最快方法（附三套完整代码注释）
导入——质数（素数）的定义
质数 ：指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
分布规律： 以36N（N+1）为单位，随着N的增大，素数的个数以波浪形式渐渐增多。
1）简单粗暴法
因为质数除了1和本身之外没有其他因数，所以判断n是否为质数，根据定义，直接从2到n-1逐个判断是否存在因数可以将n整除即可。
//完整版方法1 C++代码：
//Zhang Fan
//2019/1226/17:40
#include "stdafx.h"
#include
#include
using namespace std;
int main(){
int i,n;
cin>>n;
for(i=2;i<= n;i++){
if(n%i==0){ cout<<"no"; system("pause");return 0;}
else { cout<<"yes";system("pause");return 0;}
}//for
}
2）优化开方
上一个方法易于理解，可是效率很显著地低下。
为什么这么说？因为我们在对一个数n进行因数分解时，得到的两个数一定是一个小于等于√n，一个大于等于√n 的。
举个例子 ： 6=1×6=2×3 ，√6≈2.45。
这里不是想说6不是质数这个简单的知识，而是 因数2 和 因数3 分布在了√6的两侧。遍历过程从小到大，如果遍历到因数3那么一定遍历过因数2，而在碰到因数2的时候判断就停止了。
所以，上述代码中并不需要遍历到n-1，遍历到 √n 即可。
//完整版方法2 C++代码：
//Zhang Fan
//2019/1226/17:40
#include "stdafx.h"
#include
#include
#include
using namespace std;
int main(){
int n;
cin>>n;
float tmp;
tmp=floor(sqrt((float)n));
for(int i= 2; i <=tmp; i++){
if(n %i== 0){ cout<<"no";system("pause");
return 0 ;}
}//for
//如果能走出for循环，证明n是素数
cout<<"yes";system("pause");
return 0 ;
}
3）继续优化
方法2时间复杂度是O(sqrt(n))，已经比方法1的O(n)快了很多。那么还有没有更好的方法呢？
这里要引入一个性质：质数总是等于 6x-1 或者 6x+1，其中 x 是自然数。
证明：令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
我们从6x开始，逐一进行判断：
6x 肯定不是质数，是偶数，6x=6*x；
6x+1 不一定；
6x+2 肯定不是质数，是偶数，6x+2=2*(3x+1)；
6x+3 肯定不是质数，6x+3=3*(2x+1)；
6x+4 肯定不是质数，是偶数，6x+4=2*(3x+2)；
6x+5 不一定；
所以，质数只可能出现在6x的相邻两侧（但在6的倍数相邻两侧并不是一定就是质数，如 35，所以需要进一步判断）。 ——第一次if判断
既然如此，我们可以以 6 作为阶梯逐步增大到 √n，每次只判断6x-1和6x+1，来遍历所有可能的因数。 ——第二次if判断
完整版方法3 代码：
//完整版方法3 C++代码：
//Zhang Fan
//2019/1226/17:40
#include "stdafx.h"
#include
#include
#include
using namespace std;
int main(){
int n;
cin>>n;
if(n==2 || n==3) { cout<<"yes";system("pause");return 0; }
if(n%6!=1 && n%6!=5){//如果不在6x的左右两侧，直接可以判断不是质数
cout<<"no"; system("pause");return 0;}
float n_sqrt;
n_sqrt=floor(sqrt((float)n));
for(int i=5;i<=n_sqrt;i+=6){
if(n%(i)==0 | n%(i+2)==0) { cout<<"no";
system("pause");
return 0;}
}//for
//能走到这里证明已经经过了所有检验，是一个合格的质数了
cout<<"yes";system("pause");return 0;
}
/*也有写做如下的，一样的想法，都是（左边 = 6x-1，右边 = （6x-1）+ 2）
for(int i= 5;i <=tmp; i+=6 )
if(num %i== 0||num %(i+ 2)==0 )
*/
因为每6个数中只需判断2个，理论上讲整体速度应该会是方法2的3倍。
注：如有不足欢迎指出，笔者一定虚心思考接受！