看起来貌似是个很没营养的问题，网上一搜一大堆，粗制滥造的答案看就能看吐。
求质数，比如：
求 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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
<?php $m = 1; $n = 10000; $result = array(); $next = 0; for ($i = $m; $i <= $n; ++$i) { for ($x = 2; $x <= sqrt($i); ++$x) { $Modulo = $i % $x; if ($Modulo == 0) { //echo 'Number '.$i.' is not Prime number'."\n"; $flag = false; break; } } if ($flag) { $result[] = $i; } $flag = true; } print_r($result); echo count($result)."\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之间的所有质数
|
1 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 31 32 33 |
<?php $n = 100000; $result = array(2); $next = 1; while (true) {//预留 $next = $next + 2;//直接判断奇数，跳过所有偶数 if ($next >= $n) { break;//已满足所求数量条件，结束 } $flag = false;//初始化flag foreach ($result as $x) { if ($x > sqrt($next)) {//没有找到能范围内能整除此数的质数，这个数字也是质数 //echo 'Number '.$next.' is Prime number'."\n"; $flag = true; break; } $Modulo = $next % $x; if ($Modulo == 0) { //echo 'Number '.$next.' is not Prime number'."\n"; break; } } if ($flag) { $result[] = $next;//将这个数字放入结果数组 //echo 'count is '.count($result)."\n"; } } print_r($result); echo count($result)."\n"; |
问题2
第二个问题： 从 1 开始，求 N 个质数
我们的算法是在判断条件达成后结束的，那么我们把判断条件向后延伸就好了。
代码：从 1 开始，求 N 个质数
|
1 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 31 32 33 34 35 |
<?php $n = 10000;//十万太多，一万个就好了 $result = array(2); $next = 1; while (count($result) < $n) {//检查$reslut中保存了多少个结果，满足结果后就退出 $next = $next + 2;//直接判断奇数，跳过所有偶数 /* if ($next >= $n) { break;//现在用不到这个条件了 } */ $flag = false;//初始化flag foreach ($result as $x) { if ($x > sqrt($next)) {//没有找到能范围内能整除此数的质数，这个数字也是质数 //echo 'Number '.$next.' is Prime number'."\n"; $flag = true; break; } $Modulo = $next % $x; if ($Modulo == 0) { //echo 'Number '.$next.' is not Prime number'."\n"; break; } } if ($flag) { $result[] = $next;//将这个数字放入结果数组 //echo 'count is '.count($result)."\n"; } } print_r($result); echo count($result)."\n"; |
从1开始的新思路
问题1
我们刚才做了一件有趣的事，我们在查找从 2 到 N 之间的时候，把所有偶数都刨除去了，因为我们可以很清楚的确定，偶数就是能被2整除的数字，那么除了2这个特例之外，其他大于2的偶数都是合数，没有判断的必要。
那么我们是否有办法把能被3整除的合数也都刨去？被5呢？接下来还有7、11，我们是否可以一边找到最小的质数，一边把能被这个质数整除的所有合数都刨除在接下来的判定范围内？
这就是所谓的“筛法”、“排除法”了。
代码：从 1 到 N 之间所有质数
|
1 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 31 32 33 34 35 36 37 38 |
<?php $n = 100000; $result = array(); for ($i = 2; $i <= $n; ++$i) { $result[] = $i;//首先生成一个从 2 到 100000 的连续数组。[2,3,4,5,....,99999,100000] } //print_r($result); $value = current($result);//数组指针指向第一个位置，将值赋予$value //echo $value."\n"; while ($value !== false) {//确认指针是否还没指向数组结尾的外部，如果指到了，说明已经没有要验证的值，可以结束了。其实用不到这个条件。 $result_copy = $result;//复制一个数组。因为使用foreach时改变数组长度是有风险的。复制的时候会同时复制数组内部指针。 $Prime = $value;//初始化时我们从2开始，2是个特别的质数。 if ($Prime > sqrt(max($result))) { echo 'break at $Prime '.$Prime."\n";//比当前质数平方还要大的值还没有被消除，那么他肯定是质数了。整个数组验证结束。 break; } //echo 'While $Prime='.$Prime."\n"; foreach ($result as $i => $value) {//循环数组 if ($value <= $Prime) { continue;//假如循环到的数比正在准备的质数还小，就跳过。比如当我们判断数组中被3整除的数的时候，仍然会从第一个2开始，没有比较的必要，跳过。 } $Modulo = $value % $Prime; //echo $value.' % '.$Prime.' = '.$Modulo."\n"; if ($Modulo == 0) { //echo 'Number '.$value.' is not Prime number'."\n"; unset($result_copy[$i]);//当我们判定此数会被质数整除时，从数组中剔除这个元素。注意剔除的是复制数组的。 } } //print_r($result_copy); $result = $result_copy;//将被剔除元素的复制数组赋给原数组 //echo current($result)."\n"; $value = next($result);//继续循环 } $result = array_values($result); //print_r($result); echo count($result)."\n"; |
上面的代码可能写的比较繁琐。如果要表达的简单一些，那么我们举例 $n = 30，则初始化后 $result 的样子是：
[2 3 5 7 9 11 13 15 17 19 21 23 25 27 29]
（注意这个时候php数组会变成关联数组，key将不是连续的，但不影响使用foreach或next等方法）
[2 3 5 7 11 13 17 19 23 25 29]
[ 2 3 5 7 11 13 17 19 23 29]
之后应该是 7 了，但是 7 的平方是 49 ，已经超出29了，所以判断结束。我们就能得到结果数组。
注意如果不使用 array_values 的话，php数组的key不是关联数组，其状态会是这样的：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Array ( [0] => 2 [1] => 3 [3] => 5 [5] => 7 [9] => 11 [11] => 13 [15] => 17 [17] => 19 [21] => 23 [27] => 29 ) |
执行 array_values 之后才会变成：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Array ( [0] => 2 [1] => 3 [2] => 5 [3] => 7 [4] => 11 [5] => 13 [6] => 17 [7] => 19 [8] => 23 [9] => 29 ) |
注意： 在foreach循环时，unset数组是有风险的。
问题2
问题二就开始难办了。我们的筛选法是将已有范围内的不符合条件的值剔除，而会被剔除多少是不确定的，所以我们不能确定自定义范围内会被剔除多少，会剩余多少，想要得到N个质数就开始变得没办法了。
这个时候就捧出我也不理解的：素数定理。
最简单的公式：π(x)≈x/ln x，对正实数x，定义π(x)为素数计数函数，亦即不大于x的素数个数。
那么我们要获取一万个素数个数，x/ln x = 10000 他们的范围应该是 1 – x。虽然我不知道怎么算。这个方法是有误差的，在维基百科有误差表，可以根据其最大误差扩大计算范围，之后把多余的 array_splice 掉（用array_slice保留所需的也可以）。这里就不写代码了。
从 M 开始
求 从 M 到 N 之间所有质数 这种问题，对于传统试除法来讲，就是个扩展计算范围而已。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
$n = 10000; $result = array(); $next = 0; for ($i = 1; $i <= $n; ++$i) { for ($x = 2; $x <= sqrt($i); ++$x) { $Modulo = $i % $x; if ($Modulo == 0) { //echo 'Number '.$i.' is not Prime number'."\n"; $flag = false; break; } } if ($flag) { $result[] = $i; } $flag = true; } print_r($result); echo count($result)."\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 之间所有质数
|
1 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 |
<?php $m = 1; $n = 20; $json = file_get_contents('primelist.json'); $data = json_decode($json, true); $PrimeList = $data['result']; //print_r($PrimeList); $min_flag = false; $max_flag = false; $length = 0; foreach ($PrimeList as $key => $value) { //echo $value."\n"; if ($value >= $m && !$min_flag) { $first = $key; $min_flag = true; } if ($min_flag && $value <= $n) { ++$length; } if ($value > $n) { break; } } $result = array_slice($PrimeList, $first, $length); print_r($result); |
- 从 M 开始，求 N 个质数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
<?php $m = 1; $n = 20; $json = file_get_contents('primelist.json'); $data = json_decode($json, true); $PrimeList = $data['result']; //print_r($PrimeList); $min_flag = false; $max_flag = false; $length = $n; foreach ($PrimeList as $key => $value) { //echo $value."\n"; if ($value >= $m && !$min_flag) { $first = $key; $min_flag = true; break; } } echo $first."\n"; $result = array_slice($PrimeList, $first, $length); print_r($result); |
注意：以上代码均未进行过严密测试！所有边界值相关问题均未考虑！
请勿在生产环境中直接使用！
2 comments
慕若曦
2016 年 11 月 1 日 在 下午 1:36 (UTC 8) Link to this comment
仰视大神，明显本宝宝看晕了
萃香西瓜
2016 年 11 月 1 日 在 下午 8:58 (UTC 8) Link to this comment
文章思路和细节写的都很棒
查表是标准的工业用法
但是如果蛋疼地想更快求更大的第N个素数。。。
一般在基础筛法上还有些优化，最常用的是分段筛
分段筛上再结合一些基于查表的优化（比如把前x个素数的倍数预先都干掉）以及多线程处理可以优化到极致
另一个极致的方面通常是出自理论派之手，比如先用黎曼函数或者欧拉对数积分来预估第n个素数的值，然后用pi(n)或者LMO等方法来判断是大是小，最后再接分段筛甚至miller-rabin都可以
但是知道这些并不会让你的工资变得更高。。。无论是临时百度一个试除，或者是google一个素数库，或者是直接用上查表
因为你找不到让你发挥已有能力的环境