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

代码:

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

发表评论

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