素数（质数）判断的五种方法

素数判断的五种方法

素数判断是我们写程序过程中经常遇见的一个问题，于是今天我简单地整理一下常用的素数判断的方法。

素数的介绍

素数定义

质数(prime number)又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2。 --------360百科

第一种：暴力筛选法

思路分析

根据素数的定义，我们可以简单地想到：若要判断n是不是素数，我们可以直接写一个循环（i从2到n-1，进行n%i运算，即n能不能被i整除，如被整除即不是素数。若所有的i都不能整除，n即为素数）。

代码实现

boolean isPrime(int n){

for(int i=2;i

if(n%i==0){

return false;

break;

}

}

return true; // 反之则返回true

}

时间复杂度：O(n)

这时间复杂度一看就不咋乐观，于是我们简单优化一下。

boolean isPrime(int n){

for ( i=2; i<=(int)sqrt(n); i++ ){//如果n被i整除，则返回false

if(n%i==0){

return false;

break;

}

}

return true; // 反之则返回true

}

时间复杂度：O(sqrt(n))

优化原理：素数是因子为1和本身， 如果num不是素数，则还有其他因子，其中的因子，假如为a,b.其中必有一个大于sqrt(num) ，一个小于sqrt（num） 。所以必有一个小于或等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。即一个合数一定含有小于它平方根的质因子。

第二种：素数表筛选法

素数表筛选法一看名字就知道是将素数存到一个表中，然后对需要判断的数在表中查找，找了就是素数，找不到的即不是素数。

思路分析

如果一个数不能整除比它小的任何素数，那么这个数就是素数

顺便嘀咕一句，这种方法的效率贼低，看看就好，学习一下思路就行。

代码实现

/*

target:要查询的数字

count:素数表中素数的个数

PrimeArray:素数表数组

*/

boolean isPrime(int target, int count, int[] PrimeArray){

for (i = 0; i < count; i++){

if (target % PrimeArray[i] == 0){

return false;

break;

}

}

return true;

}

时间复杂度：O(n)

第三种：埃拉托斯特尼(Eratosthenes)筛法

思路分析

创建一个比范围上限大1的数组，我们只关注下标为 1 ~ N（要求的上限） 的数组元素与数组下标对应。 将数组初始化为1。然后用for循环，遍历范围为：[2 ~ sqrt(N)]。如果数组元素为1，则说明这个数组元素的下标所对应的数是素数。 随后我们将这个下标（除1以外）的整数倍所对应的数组元素全部置为0，也就是判断其为非素数。 这样，我们就知道了范围内（1 ~ 范围上限N）所有数是素数（下标对应的数组元素值为1）或不是素数（下标对应的数组元素值为0）

例子（N=25）

详细列出算法如下： 1、列出2以后的所有序列： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2、标出序列中的第一个素数，也就是2，序列变成： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 3、将剩下序列中，划掉2的倍数，序列变成： 2 3 5 7 9 11 13 15 17 19 21 23 25 4、如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。 5、本例中，因为25大于2的平方，我们返回第二步： 6、剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成： 2 3 5 7 11 13 17 19 23 25 7、我们得到的素数有：2，3 8、25仍然大于3的平方，所以我们还要返回第二步： 9、序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成： 2 3 5 7 11 13 17 19 23 10、我们得到的素数有：2，3，5 。 11、因为23小于5的平方，跳出循环。

结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

代码实现

/*

target:要查询的数字

isprime:素数数组，大小至少为n+1

n:数值上界

*/

boolean isPrime(int target,int[] isprime, int n){

isprime[2]=0;

int k=2,tt=0;

while(tt

for(int i=1; i

if(i%k==0&&i!=k) isprime[i]=1;

}

for(int i=1; i

if(i>k&&isprime[i]==0){

k=i;

break;

}

}

tt++;

}

if(isprime[target]==1)return true;

else return false;

}

时间复杂度：O(n^3)

第四种：线性筛选–欧拉筛法

思路分析

在埃拉托斯特尼(Eratosthenes)筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

代码实现

void PrimeList(int* Prime, bool* isPrime, int n) {

int i = 0, j = 0, count = 0;

if (isPrime != NULL) {//确保isPrime不是空指针

//将isPrime数组初始化为 1

for (i = 2; i <= N; i++) {

isPrime[i] = true;

}

}

if (isPrime != NULL && Prime != NULL) {

//从2遍历到范围上限N

for (i = 2; i <= N; i++) {

if (isPrime[i])//如果下标（下标对应着1 ~ 范围上限N）对应的isPrime值没有被置为false，说明这个数是素数，将下标放入素数数组

Prime[count++] = i;

//循环控制表达式的意义：j小于等于素数数组的个数 或 素数数组中的每一个素数与 i 的积小于范围上限N

for (j = 0; (j < count) && (Prime[j] * (long long)i) <= N; j++)//将i强制转换是因为vs上有warning，要求转换为宽类型防止算术溢出。数据上不产生影响

{

isPrime[i * Prime[j]] = false;//每一个素数的 i 倍（i >= 2）都不是素数，置为false

//这个是欧拉筛法的核心，它可以减少非素数置false的重复率

//意义是将每一个合数（非素数）拆成 2（最小因数）与最大因数 的乘积

if (i % Prime[j] == 0)

break;

}

}

}

}

时间复杂度：O(n)

第五种：欧拉筛法优化

由上面欧拉筛法的代码可见，欧拉筛法的代码也挺臃肿的，于是我们简单优化一下。

代码实现

boolean isPrime(int num) {

if (num <= 3) {

return num > 1;

}

// 不在6的倍数两侧的一定不是质数

if (num % 6 != 1 && num % 6 != 5) {

return false;

}

int sqrt = (int) Math.sqrt(num);

for (int i = 5; i <= sqrt; i += 6) {

if (num % i == 0 || num % (i + 2) == 0) {

return false;

}

}

return true;

}

结束语

本文部分参考以下文章： https://zhuanlan.zhihu.com/p/104314640

如有问题，欢迎留言交流，共同进步