«

»

31 2016

PHP求质数

看起来貌似是个很没营养的问题,网上一搜一大堆,粗制滥造的答案看就能看吐。

求质数,比如:

求 N 是否为质数?那就从 i=2 一直遍历到 i=N-1 之后求余呗,只要余数有为 0 的,那 N 就不是质数————这是不少网上教程给出的答案,可能不少计算机专业老师也是这么教课的。

衍生题目还有:

  • 求 从 1 到 N 之间所有质数
  • 从 1 开始,求 N 个质数
  • 求 从 M 到 N 之间所有质数
  • 从 M 开始,求 N 个质数

自计算机编程开始低廉化之后,太多的人蜂拥涌入软件开发行业,以Java和Android为潮流,低效低质量的软件和代码层出不穷。编程从一门优雅的艺术变成了堆满劣质农家肥的垃圾场。

 

书本算法

从1开始的传统思路:试除

除了1和该数自身外,无法被其他自然数整除的数,即为质数。则确认 一个数 是否为素数的最基本方法,就是将 这个数 除以每个大于1且小于等于 其自身 的整数 m。若余数为0,则这个数不是质数。反之则是。

这种方法就叫做:试除法

问题1

先考虑最基本问题:从 1 到 N 之间所有质数

首先就要把 i=2 一直遍历到 i=N-1 之后求余 这种方法掀翻了。

假如问 101 是否为质数,难道还要验证一下 101 % 100 是否为 0 吗?多余。

要遍历的最后一个值应该是 N的平方根取整 sqrt(101),只要验证 101 % 10 是否为 0 就可以了。等到11的时候,11 * 11 = 121 ,已经大于 101 了,没必要计算。

维基百科上关于试除法的定义:

测试 n 是否为素数的最基本方法为试除法。此一程序将 n 除以每个大于1且小于等于 n 的平方根之整数 m。若存在一个相除为整数的结果,则 n 不是素数;反之则是个素数。

代码:


但对于从1开始的方法,我们还可以继续考虑:

所有大于2的偶数都是合数,这个毫无争议,所以应该跳过所有对大于2的偶数的判断。

接下来,每一合数都可以以唯一形式被写成质数的乘积,算术基本定理。那么只要验证一个数不可以被其他质数整除,那么他就是质数。缩小原有范围(无法被其他自然数整除的数)。

比如要验证 49 是否为质数,则验证 49 % 2 和 49 % 3 之后,没有必要去验证 49 % 4 或 49 % 6,可以跳过 4 直接验证 5,跳过 6 直接验证 7。

我们的计算就会简化为:

数组$result 保存从1到i-1之间所有的质数,为确定数i是否为质数时,确认N是否可以被 数组$result 中的任何一个数整除,如全部都不能,i就是质数。

代码:求1-100000之间的所有质数


 

问题2

第二个问题: 从 1 开始,求 N 个质数

我们的算法是在判断条件达成后结束的,那么我们把判断条件向后延伸就好了。

代码:从 1 开始,求 N 个质数


 

从1开始的新思路

问题1

我们刚才做了一件有趣的事,我们在查找从 2 到 N 之间的时候,把所有偶数都刨除去了,因为我们可以很清楚的确定,偶数就是能被2整除的数字,那么除了2这个特例之外,其他大于2的偶数都是合数,没有判断的必要。

那么我们是否有办法把能被3整除的合数也都刨去?被5呢?接下来还有7、11,我们是否可以一边找到最小的质数,一边把能被这个质数整除的所有合数都刨除在接下来的判定范围内?

这就是所谓的“筛法”、“排除法”了。

代码:从 1 到 N 之间所有质数


上面的代码可能写的比较繁琐。如果要表达的简单一些,那么我们举例 $n = 30,则初始化后 $result 的样子是:

[2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30]
第一次循环时,$Prime 为 2,并且会把 $result 中所有大于 2 的值全部判断一下,能被整除的统统 unset 掉,之后$result 的样子是:
[2 3 5 7 9 11 13 15 17 19 21 23 25 27 29]
(注意这个时候php数组会变成关联数组,key将不是连续的,但不影响使用foreach或next等方法)
之后我们使用 next() 取数组中的下一个值,$Prime 为 3,并且会把 $result 中所有大于 3 的值全部判断一下,能被整除的统统 unset 掉,之后$result 的样子是:
[2 3 5 7 11 13 17 19 23 25 29]
之后是 5:
[ 2 3 5 7 11 13 17 19 23 29]

之后应该是 7 了,但是 7 的平方是 49 ,已经超出29了,所以判断结束。我们就能得到结果数组。

注意如果不使用 array_values 的话,php数组的key不是关联数组,其状态会是这样的:


执行 array_values 之后才会变成:


注意: 在foreach循环时,unset数组是有风险的。

 

问题2

问题二就开始难办了。我们的筛选法是将已有范围内的不符合条件的值剔除,而会被剔除多少是不确定的,所以我们不能确定自定义范围内会被剔除多少,会剩余多少,想要得到N个质数就开始变得没办法了。

这个时候就捧出我也不理解的:素数定理。

最简单的公式:π(x)≈x/ln x,对正实数x,定义π(x)为素数计数函数,亦即不大于x的素数个数。

那么我们要获取一万个素数个数,x/ln x = 10000 他们的范围应该是 1 – x。虽然我不知道怎么算。这个方法是有误差的,在维基百科有误差表,可以根据其最大误差扩大计算范围,之后把多余的 array_splice 掉(用array_slice保留所需的也可以)。这里就不写代码了。

从 M 开始

求 从 M 到 N 之间所有质数 这种问题,对于传统试除法来讲,就是个扩展计算范围而已。


虽然我们的新试除方法看起来更有效率,但是其从2开始的思路无法直接完成 求 从 M 到 N 之间所有质数 这种需求。唯一的解决办法就是,计算出 从 1 到 N 之间所有质数,再把小于 M 的全部删掉。

同理从 M 开始,求 N 个质数也会有这种问题。

而筛法则同样会面临同样的问题。越是有效率的方法,怎么感觉越是没法大范围使用?

工业用法

上面讲了那么多,其实都是理论派、学院派用法。实际工作中,对于质数这种永恒不变的数值,最快的方法,也是最简单高效的方法:查表

对,没看错,查表!

这就相当于你告诉一个不会乘法只会加法的小孩,告诉他 7*9 就是 7个9加到一起,他会7+7+7+7+7+7+7+7+7=63这么计算,而会乘法口诀之后,只要七九六十三,便能瞬间得到答案。

 

我们首先估算我们所需要的质数范围,之后使用筛法计算出所需要的质数范围,保存到固定文件中。当需要使用时,读取这个文件,再从文件中取出所需内容。这样四个问题都轻易解决:

我们得到足够大的质数表:primelist.json

  • 求 从 M 到 N 之间所有质数

 

  • 从 M 开始,求 N 个质数

注意:以上代码均未进行过严密测试!所有边界值相关问题均未考虑!

请勿在生产环境中直接使用!

2 comments

  1. 慕若曦

    仰视大神,明显本宝宝看晕了

  2. 萃香西瓜

    文章思路和细节写的都很棒
    查表是标准的工业用法

    但是如果蛋疼地想更快求更大的第N个素数。。。
    一般在基础筛法上还有些优化,最常用的是分段筛
    分段筛上再结合一些基于查表的优化(比如把前x个素数的倍数预先都干掉)以及多线程处理可以优化到极致

    另一个极致的方面通常是出自理论派之手,比如先用黎曼函数或者欧拉对数积分来预估第n个素数的值,然后用pi(n)或者LMO等方法来判断是大是小,最后再接分段筛甚至miller-rabin都可以

    但是知道这些并不会让你的工资变得更高。。。无论是临时百度一个试除,或者是google一个素数库,或者是直接用上查表

    因为你找不到让你发挥已有能力的环境

发表评论

电子邮件地址不会被公开。 必填项已用*标注