分解质因数

今天空闲，忽然想到一个挺有意思的小学学过的内容，分解质因数！
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。
看起来很容易的样子，但怎么用程序计算出来呢？今天来研究下算法。

比如要分解一个很大的数的质因数，比如 PHP_INT_MAX，应该怎么做呢？
算法一：获取 PHP_INT_MAX 内所有的质数，循环一下，挑出质数放入数组 $primes。
算法二：用递归方法，从小到大循环 $primes 内所有数，看是否能被 PHP_INT_MAX 整除，如能整除则将些数放入数组 $factor，再递归调用自己至到不能被整除后计算下一个数是否能被整除，直到循环结束。

说起来很简单，先来研究获取质数算法。
在网上看到个思路：

function get_prime($max_num){
    $max_num = floor($max_num);
    $prime = array();
    for($x = 1; $x <= $max_num; $x++){
        $flag = true; // 当flag为false时表示该数不是素数
        for($y = 2; $y < $max_num; $y++){ //$y从2开始，因为除数为1时，肯定能整除
            if($x > $y){ // $y如果比$x还大，取模肯定不为0，没有比较的意义
                if($x % $y == 0 ){ //当除数$y为$x以内时，如果取模为0，表示该数不是素数
                    $flag = false;
                }
            }
        }
        if($flag) $prime[] = $x; // 如果$flag为真，则$x是质数
    }
    array_shift($prime); // 把1从质数数组中剔除
    return $prime;
}

双层循环，循环次数根据 $max_num 变大而成指数上升，效率非常低！

后来想到可以用试除法判定质数，如下：

function is_prime1($n) {
    if($n < 2) return false;
    for($i = 2; $i < $n; $i++){
        if($n % $i == 0) return false;
    }
    return true;
}

但是，也可以看出但是了，时间复杂度是O(N)，很容易看出若n是一个很大的数会导致超时！

对上面代码进行了下改进：

由于判定n是否为质数。根据质数的性质,若在2~sqrt(n)中没有可以把它整除的，那么在sqrt(n)~n-1中也没有可以把n整除的，因此可以改进为以下三种写法，此时时间复杂度为O()：

function is_prime2($n){
    if ($n < 2) return false;
    for ($i = 2; $i * $i <= $n; $i++) {
        if ($n % $i == 0) return false;
    }
    return true;
}

function is_prime3($n){
    if($n < 2) return false;
    $t = sqrt($n);
    for($i = 2; $i <= $t; $i++){
        if($n % $i == 0) return false;
    }
    return true;
}

function is_prime4($n){
    if($n < 2) return false;
    for($i = 2; $i <= $n / $i; $i++){
        if($n % $i == 0) return false;
    }
    return true;
}

经过分析提倡is_prime4()的写法，因为is_prime2()的写法在判断 i * i ≤ n 时，i * i可能大于整型范围从而导致溢出，进而影响结果。不推荐使用is_prime3()是因为在调用sqrt(n)函数时可能会导致超时，因此综合分析is_prime4()是最合适的。

算法二：很简单的，不用解释太多

function resolving(&$factor, $num, $primes, $i=0){
    if(!is_int($num) || $num < 0) return;
    if(in_array($num, $primes)){
        // 如果该数为质数
        $factor[] = $num;
    } else {
        $ceil = ceil($num / $primes[$i]);
        if($ceil == ($num / $primes[$i])){
            $factor[] = $primes[$i];
            // 如果当前质数还能被$ceil整除，则继续用该质数(不用$i++)
            // 比如90分解为2、3、3、5，否则让$i++再递归
            if($ceil % $primes[$i]!=0) $i++;
            resolving($factor, intval($ceil), $primes, $i);
        } else {
            // 对于99这样的，不是质数，但也没第一次被整除的，用下一个质数($i++)测试它
            resolving($factor, $num, $primes, $i+1);
        }
    }
}

到目前为止，组装所有零件就能运行啦，效率还行！

完整代码如下：

<?php
set_time_limit(300);
function is_prime4($n){
    if($n < 2) return false;
    for($i = 2; $i <= $n / $i; $i++){
        if($n % $i == 0) return false;
    }
    return true;
}
function resolving(&$factor, $num, $primes, $i=0){
    if(!is_int($num) || $num < 0) return;
    if(in_array($num, $primes)){
        // 如果该数为质数
        $factor[] = $num;
    } else {
        $ceil = ceil($num / $primes[$i]);
        if($ceil == ($num / $primes[$i])){
            $factor[] = $primes[$i];
            // 如果当前质数还能被$ceil整除，则继续用该质数(不用$i++)
            // 比如90分解为2、3、3、5，否则让$i++再递归
            if($ceil % $primes[$i]!=0) $i++;
            resolving($factor, intval($ceil), $primes, $i);
        } else {
            // 对于99这样的，不是质数，但也没第一次被整除的，用下一个质数($i++)测试它
            resolving($factor, $num, $primes, $i+1);
        }
    }
}

// 计算目标数，如果你电脑够强的话可以试试 PHP_INT_MAX
$target = 100005;
$primes = array();
for($i = 0; $i <= $target; $i++) {
    if(is_prime4($i)) $primes[] = $i;
}

$factor = array();
resolving($factor, $target, $primes);
print_r($factor);
?>

同时做了一个JS版的，有兴趣的同学可以看看：《在线分解质因数》

分解质因数

文章评论