记一次理解并实现筛除法找素数

前提：作为一名只工作两三年的phper菜鸟且今天第一次写博客，有什么不足或者问题请多多见谅，也欢迎指正。

最近面试遇到了很多问题，本来还自信心满满的我惨遭打脸，这此的问题就是关于素数的，他的问题很简单：如何找出1-100以内的素数？

我想的很简单 详见代码 function getPrime($number){ $result = []; for ($a = 2;$a < $number;$a++){ if($a < 10){ if($a % 4 <> 0 && $a % 6 <> 0 && $a % 9 <> 0){ $result[] = $a; } }else{ if($a % 2 <> 0 && $a % 3 <> 0 && $a % 5 <> 0 && $a % 7 <> 0){ $result[] = $a; } } } return $result; }

但是他接下来就问哪1000以内呢？我第一个想到的就是试除法，具体的就是两个循环嵌套，代码如下：

function getPrime($number){ $prime = []; for ($a = 2; $a <= $number; $a++) { $flag = 0; //用于做个标识 //循环判断 for ($b = 2; $b < $a; $b++) { if ($a % $b == 0) { $flag = 1; break; } } if ($flag == 0 && $a != 1) {//1不是素数 $prime[] = $a; } } return $prime; }

我很快把这个方案给否决掉了，运算量太大，也太耗时间了，又有点紧张，一时间没有想到很好的解决办法。只有大概一个思路，就是排除法，在给定的集合中我把2的倍数，3的倍数依次剔除，那么剩下的不就是素数了，于是后面我又想了几套解决方案，代码如下：

function two($number){ if($number < 10){ return false; } $min = floor(sqrt($number));//相比较上面加了这么一步，就是所传范围的最大值开跟，即查找这个条件($a % 2 <> 0 && $a % 3 <> 0 && $a % 5 <> 0 && $a % 7 <> 0) $prime = []; for ($a = 2; $a <= $min; $a++) { $flag = 0; //用于做个标识 for ($b = 2; $b < $a; $b++) { if ($a % $b == 0) { $flag = 1; break; } } if ($flag == 0 && $a != 1) { $prime[] = $a; } } return $prime; } //获取质数 function number($number){ $prime = two($number); $result = $prime; for($a = 2;$a < $number;$a++){ foreach ($prime as $v){ if($a % $v == 0){ break; }else{ if($v == end($prime)){ $result[] = $a; } } } } return $result; } 这种方式比试除法快了很多，经测试一千万范围花了26秒左右，应该还是有优化空间的。

那么有没有比这个更快的，有，其实就是我面试大概想出的那个思路，排除法，代码如下：

function getPrime($number){ $arr=primeArr($number); $n = $number - 1;//素数个数，排除法 for ($i = 2;$i <= $number;$i++){ foreach ($arr as $v){ if($i % $v == 0){ $n--; break; } } } echo $n+count($arr); } /** * 下一个素数 */ function nextPrime($i){//下一个质数 while (true){ $i++; if($i == 2){ return $i; }elseif ($i < 2){ continue; } $is=true; for($j = 2;$j <= sqrt($i);$j++){ if($i % $j == 0){ $is = false; } } if($is){ return $i; } } } /** * 作为除数的素数数组 */ function primeArr($a){ if($a <= 1){ return []; } $arr = []; $prime=0; while ($prime <= sqrt($a)){ $prime = nextPrime($prime); $arr[] = $prime; } return $arr; } 这个就更快了一千万的数据只需要10秒左右。

到此结束：

我感觉作为普通的开发人员为什么会觉的进入瓶颈什么的，其实就是我们不愿意在细小的环节上多下功夫，大家都愿意偷懒，尤其对于什么外包公司，但是一旦思维形成惯势，再想纠正就很难了。还是希望大家包括我在这方面多下点功夫。