【算法】素数(质数)判断方法

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

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

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

我们可以从它的定义得到判断素数的 第一个方法: 从 2 2 2 到 n − 1 n - 1 n−1, 判断是否存在能被n整除的数，既 ( n % i = = 0 , 2 < = i < = n − 1 ) (n \% i == 0, 2 //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2 int j; for(j = 2; j //因为偶数除了2之外都不是素数(质数),所以只需判断奇数，从3开始每次+2 int j; for(j = 2; j (int)sqrt(i)) sum++; } printf("Time used = %0.2f s\n",(double)clock()/CLOCKS_PER_SEC); printf("%d",sum); return 0; }

程序的时间复杂度为O( n \sqrt{n} n ​)。 运行结果 可以看到程序的运行时间已经大幅度地降低。

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

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

∵ n − 1 , n + 1 是 素 数 ， 也 即 n − 1 和 n + 1 是 奇 数 ∴ n 是 偶 数 ， n 是 2 的 倍 数 。 设 n 不 是 3 的 倍 数 ， 即 n = 3 k + 1 或 n = 3 k + 2 。 ( i ) 当 n = 3 k + 1 时 ， 那 么 n − 1 = 3 k , 已 经 与 n − 1 是 素 数 矛 盾 。 ( i i ) 当 n = 3 k + 2 时 ， 那 么 n + １ ＝ 3 ( k + 1 ) , 已 经 与 n + 1 是 素 数 矛 盾 。 综 上 所 述 ， n 是 3 的 倍 数 。 ∵ n 既 是 2 的 倍 数 ， 又 是 3 的 倍 数 ∴ n 是 6 的 倍 数 。 \begin{aligned} &∵ n - 1, n + 1是素数，也即 n - 1 和 n + 1是 奇数\\ &∴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 +１＝3(k + 1),已经与 n + 1是素数矛盾。\\ &综上所述，n 是 3 的倍数。\\ &∵n既是2的倍数，又是3的倍数\\ &∴n 是6的倍数。\\ \end{aligned} ​∵n−1,n+1是素数，也即n−1和n+1是奇数∴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+１＝3(k+1),已经与n+1是素数矛盾。综上所述，n是3的倍数。∵n既是2的倍数，又是3的倍数∴n是6的倍数。​

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

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

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

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

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