Home产品研发PHP求质数-演道网

PHP求质数-演道网

2016 年 10 月 31 日









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

求质数，比如：

求 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 不是素数；反之则是个素数。

代码：

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
$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之间的所有质数

PHP

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
 
$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 个质数

PHP

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
 
$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 之间所有质数

PHP

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
 
$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 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不是关联数组，其状态会是这样的：

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 之间所有质数 这种问题，对于传统试除法来讲，就是个扩展计算范围而已。

PHP

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 之间所有质数

PHP

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
 
$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 个质数

PHP

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
 
$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);



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

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

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

Related Posts

About The Author

bjmayor

程序员，码农，php,python,ios,android,go，产品经理，创业。