一次关于素数while循环的分析

2018-02-09

今天在知乎看到一个问题同为动态语言，Python 的性能为何只有 PHP 的五分之一？，本来对于打嘴仗没有兴趣，无意中看到了一段代码，是一个while循环，改动后执行速度竟然从453ms减少到了97ms，代码如下：

<?php
function isprime($num) {
    $count = (int) sqrt($num);
    while ($count > 1) {
        if ($num % $count == 0) {
            return false;
        }
        $count-- ;
    }
    return true;
}
$start = microtime(true);
for ($i = 2; $i < 100000; $i++) {
    isprime($i);
}
echo (microtime(true) - $start) * 1000 ."\n";

改动后的代码如下：

<?php
function isprime($num) {
    $count = (int) sqrt($num);
    $i = 2;
    while ($i <= $count) {
        if ($num % $i == 0) {
            return false;
        }
        $i++ ;
    }
}
$start = microtime(true);
for ($i = 2; $i < 100000; $i++) {
    isprime($i);
}
echo (microtime(true) - $start) * 1000 ."\n";

差别只有while部分，一个是自增，一个是自减，按道理自增和自减本身并不会有速度上的差别，那只能是while执行的次数原因了

首先加一个标志$counter,while每运行一次就加1，然后查看两段代码分别计算10以内的素数的while执行次数

#第一段代码
$counter = 0;
while ($count > 1) {
    $counter++;
    if ($num % $count == 0) {
        echo $counter . 's';
        return false;
    }
    echo $counter . 's';
    $count-- ;
}

#第二段代码
$counter = 0;
$i = 2;
while ($i <= $count) {
    $counter++;
    if ($num % $i == 0) {
        echo $counter . 's';
        return false;
    }
    echo $counter . 's';
    $i++ ;
}

执行结果如下：

正如我预料的那样，第一段代码明显运行次数较多，以18的素数来说，第一段代码执行了1次，而第二段代码执行了2次。
稍微想一下就知道了原因，18的平方根取整是4。
按照代码最多执行3次，而18明显不是素数。
这就导致了在第一段代码执行了4、3的时候发现了18不是素数，第二段代码执行到2的时候就发现了。

顺便提一句，编程语言只是工具。