【算法】素数(质数)判断方法「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

注：本篇文章已搬至个人博客中, 点击前往

素数(质数)的判断在算法问题中经常遇到，这里小结几种常用的判断方法。

素数(质数)的定义

首先，我们来看一下素数(质数)的定义：质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。

方法一

我们可以从它的定义得到判断素数的 第一个方法: 从 $2$ 到 $n-1$, 判断是否存在能被n整除的数，既$(n\%i==0,2<=i<=n-1)$,如果有就不是素数，否则为素数。

(这里为了比较几种算法的性能，用计算出1000,000中有多少个素数所需的时间作为性能比较的参考。附上本篇博文所有程序的运行环境(机房哈哈)：系统windows xp, cpu:E5200,2.50GHZ, 0.99GB内存，IDE：codeblocks)

首先，可以先作一个小的优化，既除2以外，只需判断所有的奇数是否是素数。

//素数判断方法1
#include<stdio.h>
#include<time.h>
#define Max 1000000
int main()
{ 
   
    int sum = 1;//2单独处理，sum为素数的个数
    for(int i = 3; i <= Max; i+=2)
    { 
   //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2
        int j;
        for(j = 2; j < i; j++)//判断
            if(i%j == 0)break;
        if(j == i)
            sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);//获取程序运行的时间
    printf("%d",sum);
    return 0;
}

程序的时间复杂度为O($n^2$)。
运行结果

结果表明n的数量级太大时，不宜采用该方法。
同时也可以得到结论$1000,000$中有$78498$个素数。

接下来的方法其实都是对上述方法进行优化，可以很好地降低时间复杂度。
利用以下结论：对正整数$n$，如果用2到 $\sqrt{n}$之间的所有整数去除，均无法整除，则$n$为质数。

方法二

//素数判断方法2
#include<stdio.h>
#include<time.h>
#include<math.h>
#define Max 1000000
int main()
{ 
   
    int sum = 1;
    for(int i = 3; i <= Max; i+=2)
    { 
   //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2
        int j;
        for(j = 2; j <= (int)sqrt(i); j++)//利用上述结论判断
            if(i%j == 0)break;
        if(j > (int)sqrt(i))
            sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);
    printf("%d",sum);
    return 0;
}

程序的时间复杂度为O($\sqrt{n}$)。
运行结果

可以看到程序的运行时间已经大幅度地降低。

接下来的方法需要利用到孪生素数的一些特点和结论。

孪生素数

孪生素数：孪生素数指的是间隔为 $2$ 的相邻素数。
1.当$n>=6$, $n-1$ 和 $n+1$ 为孪生素数，那么n 一定是6的倍数。
Proof :

$$\begin{array}{rl}& \because n-1,n+1是素数，也即n-1和n+1是奇数\\ & \therefore n是偶数，n是2的倍数。\\ & 设n不是3的倍数，即n=3k+1或n=3k+2。\\ & (i)当n=3k+1时，那么n-1=3k,已经与n-1是素数矛盾。\\ & (ii)当n=3k+2时，那么n+\mathrm{１}＝3(k+1),已经与n+1是素数矛盾。\\ & 综上所述，n是3的倍数。\\ & \because n既是2的倍数，又是3的倍数\\ & \therefore n是6的倍数。\end{array}$$

推论1 : 当 $x>=1$, $(6x-1)$或 $(6x+1)$不是素数时，它们的质因子不包括2和3的倍数，因为$2(3x)-1,3(2x)-1,2(3x)+1,3(2x)+1$。

2.素数的分布规律:当$n>=5$时，如果n为素数，那么$n\%6=1||n\%6=5$，即n一定出现在$6x(x\ge 1)$两侧。(就是说大于等于5的素数一定是分布在6倍数的左右两侧，但在6倍数左右两侧的数不一定是素数)
Proof：
$$\begin{array}{rl}& 可以把6x附近的数用以下方式表示：\\ & \dots \dots (6x-1),6x,6x+1,2(3x+1),3(2x+1),2(3x+2),6x+5,6(x+1)\dots \dots \\ & 不在6x两侧的数为：2(3x+1),3(2x+1),2(3x+2),它们不是素数，所以素数出现在6x的两侧。\end{array}$$
  有了以上的理论基础，我们可以对方法2进一步地优化，首先不在$6x$左右的数$2,3$单独处理，接下来只要判断$6x$两侧的数是否为素数。因为合数总是可以写成素数的乘积，那么我们直接用n去除以质数就可以达到很好地优化目的。而质数一定是 $6x$ 两侧的数（推论一已证明了当$n>=5$时，n不是素数时，n 不含质因子2,3） , $6x$ 两侧的数是大于素数的集合，因此可以用 $n$ 除以 $6x$ 两侧的数即if(n % i == 0 || n % (i + 2) == 0)时，不是素数。

方法三：基于孪生素数方法筛除

//素数判断方法3
#include<stdio.h>
#include<time.h>
#include<math.h>
#define Max 1000000
using namespace std;
int main()
{ 
   
    int sum = 1;//已经将2单独处理
    int flag = 0;
    for(int i = 3; i <= Max; i+=2)
    { 
   
        if(i == 3)//3单独处理
            sum++;
         
        if(i % 6 != 1 && i % 6 !=5)
            continue;//不是6x两侧的数不是素数
        
        for(int j = 5; j <= (int)sqrt(i); j+=6)//对6x两侧的数进行判断
            if(i%j == 0 || i%(j + 2) ==0)
            { 
   
                flag = 1;
                break;
            }
            if(flag == 1)
            { 
   
                flag = 0;
                continue;
            }
        sum++;
    }
    printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC);
    printf("%d",sum);
    return 0;
}

运行结果：

方法3运行结果表明比方法2快速了许多倍，已经是很高效的算法了。

方法四:普通筛选法

更新日记：2018/1/31增加普通筛选法
比上面几种方法更快，也比较容易理解。
思想: 一个素数的倍数都不是素数。
时间复杂度: O(nloglogn)

#include<iostream>
#include<vector>
using namespace std;
const int maxt = 1000000;
vector<bool>prime;
int main()
{ 
   
	prime.resize(maxt,1);
	prime[0] = prime[1] = 0;//1是素数，0是非素数
	for(int i = 2; i*i <= prime.size(); i++)
	{ 
   
		if(prime[i] == 1)
		for(int j = i*2; j <= prime.size(); j += i)
		{ 
   
			prime[j] =  0;
		}
	}
	return 0;
}

相关习题：蓝桥杯 Torry的困惑(基本型)