本文参考博文判断一个数是不是质数(素数)，3种方式介绍，原文章解释的已经很详细，本问增加部分博主自己的理解。
一、概念介绍
质数：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。特别的0,1不是质数。
二、方法介绍
1.最直接的方法
bool isPrime(int n){
if(n<=3){
return n>1;
}
for(int i=2; i if(n%i==0){ return false; } } return true; } 直接从2遍历到n-1，判断是否存在i，i大于等于2，小于等于n-1，且i为n的一个因数，若存在，那么n不是质数，若不存在，那么n是质数。 2.初步优化 bool isPrime(int n){ if(n<=3){ return n > 1; } int s = (int)sqrt(n); for(int i=2; i<=s; i++){ if(n%i==0){ return false; } } return true; } 其实可以看出，i只要遍历到根号下n即可。 因为倘若n为合数，存在一个因数y大于1且不等于n，那么n一定小于等于根号下n，没必要遍历到n-1。 2.5 基于奇偶数优化 bool isPrime(int n){ if(n<=2) return n==2; if(n%2==0) return false; for(int i=3; i*i if(n%i==0){ return false; } } return true; } 3.继续优化 bool isPrime(int n){ if(n<=3){ return n>1; } if(n%6!=1 && n%6!=5){ return false; } int s = (int)sqrt(n); for(int i=5; i<=s; i+=6){ if(n%i==0 || n%(i+2)==0){ return false; } } return true; } 继续分析可以发现，所有质数(除了2)总是等于6x-1或者6x+1，其中x为大于等于1的自然数。即所有质数(除了2)对6求余数，余数总是等于5或者1。（若质数为6x-1，那么余数为5，若质数为6x+1那么余数为1）。证明如下: 首先 6x 肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。 在代码中，首先判断小于等于3时的情况，若为0、1返回false;为2、3返回true; 然后判断该数是否等于6x-1或者6x+1，若不等于，那么一定不是质数，如果等于，那么不一定是质数，需要继续判断。 到现在已经保证该数等于6x-1或者6x+1，如果这个数是合数，那么他的因数一定不是2、3、4、6。它的因数只可能是6x+1或者6x+5(6x+5与6x-1相同)，即如果这个数是合数，那么他的因数只能是5(6x-1)、7(6x+1)、11(6x-1)、13(6x+1)、、、、、sqrt(n)。那么与方法二类似的，可以得到需要遍历两次，分别为：遍历的初始值为5，终值为sqrt(n)，步长为6。遍历的初始值为7，终值为sqrt(n)，步长为6。这连个遍历可以写在一起，即代码中的: for(int i=5; i<=s; i+=6){ if(n%i==0 || n%(i+2)==0){ return false; } }