曾经第一次面试题中的题目, 今天碰巧看到整理一下
当时用了最基本的算法写出来了, 两个for循环, 一个一个取余, 是质数就放进结果数组中
代码如下, 检查代码运行时间的代码是来对比三种不同算法的优劣性
算法一: 每个数都从2开始除, 除遍所有比自己小的整数, 如果有能整除的, 说明不是质数, 退出本次循环, 进行下一次循环
function test() { $start = microtime(true); //程序开始时间 // 一定要加true !!! // 一定要加true !!! // 一定要加true !!! $array = array(); //存放质数 for ($i=2; $i < 40001; $i++) { $mark = 0; //是否质数的标记 0质数, 1非质数 for ($j=2; $j < $i; $j++) { if(($i % $j) === 0) { $mark = 1; //有能整除的就说明不是质数, 退出本次循环 break; } } if($mark != 1) { $array[] = $i; //存放质数 } } echo "<pre>"; print_r($array); echo "<br>"; echo microtime(true)-$start; }
面试官看了后让我优化一下算法, 当时我的代码连break好像都没有, 然后我就加了句break, 然后信心满满的看着他,
哈哈, 然后你可以想象下他的表情了~
不过, 他人还挺好, 告诉我并不需要每次都除到比自己小1的那个数, 我第一反应是除到一般就够了,
然后他说, 除到这个数的平方根就可以了, 比如17除到4就行了, 因为当除数超过平方根后, 再除只是把商和除数的位置颠倒了而已, 是一种重复
算法二: 除了把第二个for循环中的$i 换成 sqrt($i) 之外基本没什么变化
function test1() { $start = microtime(true); $array = array(); for ($i=2; $i < 40001; $i++) { $mark = 0; for ($j=2; $j <= sqrt($i); $j++) { if(($i % $j) === 0) { $mark = 1; break; } } if($mark != 1) { $array[] = $i; } } // echo "<pre>"; // print_r($array); echo "<br>"; echo microtime(true)-$start; }
当然还有一种算法, 质数是什么? 非质数是什么?
质数就是除了自己和1 之外不能被任何数整除, 非质数就是合数, 而合数则肯定可以由质数相乘得到.
通过这个规则, 我们就可以只检查$i 是否可以整除比自己小的质数了, 非质数可以丢掉不管了.(此时的效率还不如算法二高)
还可以再结合算法二, 只检查比$i平方根小的质数, (这时的效率就比算法二高了)
算法三: 这种算法效率最高
function test2() { $start = microtime(true); $queue = array(); //用一个数组来模拟队列, 发现质数就放到队列尾部, $queue[] = 2; for ($i=2; $i < 40001; $i++) { $mark = 0; foreach ($queue as $key => $value) { //只检查比$i平方根小的质数 if($value >= sqrt($i)) { break; } //foreach循环队列, 如果能整除队列中的质数, 则说明$i不是质数, 应该立刻跳出循环 if(($i % $value) === 0) { $mark = 1; break; } } if($mark != 1) { $queue[] = $i; //如果$i是质数, 追加到队列尾部, 方便下次循环使用 } } // echo "<pre>"; // print_r($queue); echo "<br>"; echo microtime(true)-$start; }
你可以依次运行
test();
test1();
test2();
来检查结果和代码运行时间, 运行前请根据需要打开或者关闭注释