判断⼀个数是否为质数（素数）的4种⽅法
⽬录
1.什么是质数？
⾸先来看质数的概念：
质数（Prime number），⼜称素数，指在⼤于1的⾃然数中，除了1和该数⾃⾝外，⽆法被其他⾃然数整除的数。（也可定义为只有1与该数本⾝两个正因数的数）
图1  数字12不是质数，⽽数字11是质数
如上图所⽰，数字12可以将每4个分成⼀组，⼀共3组；⽽数字11将每4个、每5个、每3个分成⼀组都⽆法全部分完，⽽有剩余，因此将数字11称为质数。
2.如何判断是否为质数？
质数的特点如下：
⼀个⾃然数（如1、2、3、4、5、6等）若恰有两个正约数（1及此数本⾝），则称之为质数。
⽅法1
根据质数的约数只有1和本⾝这⼀特点，可以⾸先想到最直观的⽅法。第⼀种⽅法就是判断⼀个数是否能被⽐它⼩的数整除。
⽅法1的时间复杂度是O(n)。
public static boolean isPrime(int n){
//n<=3时，质数有2和3
if (n <= 3) {
return n > 1;
}
//当n>3时，质数⽆法被⽐它⼩的数整除
for(int i = 2; i < n; i++){
if (n % i == 0) {
return false;
}
}
return true;
}
⽅法2
当⼀个数不是质数时，必定存在两个约数，⼀个⼤于等于sqrt(n)，另⼀个⼩于sqrt(n)。利⽤这种特性，可以对⽅法1进⾏改进，只判断数n 能否被⼩于sqrt(n)的数整除。
⽅法2的时间复杂度是O(sqrt(n))。
图2  筛选判断集，只选择⼩于等于sqrt(n)的集合
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
//判断⼀个数能否被⼩于sqrt(n)的数整除
int sqrt = (int)Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if(n % i == 0) {
return false;
}
}
return true;
}
⽅法3
任⼀偶数⼀定能分解为2和其他偶数/奇数的积，因此⼀个数不能被2整除，那么这个数⼀定不能被其他偶数整除。利⽤这个特点，可以对⽅法2进⾏改进，判断数n能否被⼩于sqrt(n)的奇数整除。
⽅法3的时间复杂度是O(sqrt(n)/2)。
图3  进⼀步筛选判断集，只选择⼩于等于sqrt(n)的奇数
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
//只需判断⼀个数能否被⼩于sqrt(n)的奇数整除
int sqrt = (int)Math.sqrt(n);
for (int i = 3; i <= sqrt; i += 2) {
if(n % 2 == 0 || n % i == 0) {
return false;
}
}
return true;c++判断素数
}
⽅法4
质数的分布具有特点，经过证明可以得到，（⼤于等于5的）质数⼀定和6的倍数相邻，⼀定是6x-1或6x-1。利⽤这种特性。可以对整数进⾏筛选，只判断那些是6x-1或6x-1的整数是否为质数。
图4  筛选数据集，只选择6的倍数相邻的数
证明过程如下：
令x≥1，将⼤于等于5的⾃然数表⽰如下： ······6x-1，6x，6x+1，6x+2，6x+3，6x+4······（相邻6个数为⼀组）
在以上的数字中，6x、6x+2和6x+4是偶数，⼀定不是质数；6x+3可以分解为3(2x+1)，不是质数，因此质数只能是6x-1和6x+1。
public static boolean isPrime(int n) {
if (n <= 3) {
return n > 1;
}
// 只有6x-1和6x+1的数才有可能是质数
if (n % 6 != 1 && n % 6 != 5) {
return false;
}
// 判断这些数能否被⼩于sqrt(n)的奇数整除    int sqrt = (int) Math.sqrt(n);
for (int i = 5; i <= sqrt; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。