求100之内的素质并输出(最优算法)-PHP面试题

曾经第一次面试题中的题目, 今天碰巧看到整理一下

当时用了最基本的算法写出来了, 两个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();

来检查结果和代码运行时间, 运行前请根据需要打开或者关闭注释

巴特西

求100之内的素质并输出(最优算法)-PHP面试题

最新文章

热门文章