质数较验算法比较

[Jamers]

最近想学习一下质数算法，拿了几个简单的方式去处理。

 

先看一下最最原始未通过任何优化的核心较验代码：

     function checkprime($val) {
         /**
          * 检测是否是质数，死模式
          */
         for ($i=2;$i<=sqrt($val);$i++) {
             if ($val%$i==0) {
                 return false;
             }
         }
         return true;
     }
     //循环计算2-10000个质数，耗时0.07-0.09之间

从另一个地方取来的算法：

    function isPrime($n) {//TurkHackTeam AVP production
        if ($n <= 3) {
            return $n > 1;
        } else if ($n % 2 === 0 || $n % 3 === 0) {
            return false;
        } else {
            for ($i = 5; $i * $i <= $n; $i += 6) {
                if ($n % $i === 0 || $n % ($i + 2) === 0) {
                    return false;
                }
            }
            return true;
        }
    }
    //循环计算2-10000 耗时0.02-0.04之间

[Jamers]

最后处理的质数类：50万数据本机耗时1.7-2.0之间。当前服务器耗时1.4-1.6之间。

<?php
$x = pn::getpn(500000);
var_dump($x);
//现在50万数据时间1.7-2.0之间

class pn {
    /**
     * 质数算法测试
     * 尽量优化运算时间
     * Jamers 2015.1.16
     */
     static private $start,$end;
     
     static public $prime;
     
     static function getpn($num) {
         /**
          * 主程序，计算$num以内所有质数
          */
          $result = array();
          self::$prime = str_split(str_repeat('1',$num+1));
          unset(self::$prime[0],self::$prime[1],self::$prime[4]);
          //已将初始化值赋值完毕，开始计时
          self::$start = microtime(true);
          self::filter($num);
          foreach (self::$prime as $k=>$v) {
              if (! self::isprime($k)) {
                  unset(self::$prime[$k]);
              }
          }
          self::$end = microtime(true);
          $result['count'] = count(self::$prime);
          $result['time'] = self::$end - self::$start;
          //$result['data'] = array_keys(self::$prime);
          return $result;
     }
    static private function filter($val) {
        /**
         * 个人优化算法，过滤掉明显不符合条件的值
         * 去掉这个算法,50万数据相关时间0.3秒左右
         */
        for ($i=6;$i<=$val;$i++) {
            if (($i % 2 === 0) || ($i % 3 === 0) || ($i % 5 === 0)) {
                //过滤 能被2、3、5整除的数
                unset(self::$prime[$i]);
            }
        }
    }
    static function isPrime($n) {//TurkHackTeam AVP production
        if ($n <= 3) {
            return $n > 1;
        } else if ($n % 2 === 0 || $n % 3 === 0) {
            return false;
        } else {
            for ($i = 5; $i * $i <= $n; $i += 6) {
                if ($n % $i === 0 || $n % ($i + 2) === 0) {
                    return false;
                }
            }
            return true;
        }
    }     
}
?>