求用PHP写任意数因式分解！

Question

高手来！

Answer 1

function Factorization($num) {
  for($i=2; $i<$num/2; $i+=($i==2?1:2)) {
    while( ($num % $i) == 0 ) {
      $num /= $i;
      $r[] = $i;
    }
  }
  $r[] = $num;
  return join(' * ', $r);
}$n = 20110608;
echo  Factorization($n);2 * 2 * 2 * 2 * 3 * 3 * 7 * 71 * 281

Answer 2

显然很牛！求解释 for循环中 限制条件可以$i<$num/4不

Answer 3

这是从求素数的“筛法”改变过来的限制条件 $i<$num/2
严格上说，应该是 $i < sqrt($num) 即小于 $num 的平方根
不过求平方根可能会慢一点，你可以测试一下
从极限上说 当 x 趋向为 0 时，x 的平方根趋向为 x/2
这就是不用 sqrt($num) 而用 $num/2 的原因
虽然可能要多循环几次

Answer 4

刚才测试了一下
使用 $i < sqrt($num) 要比使用 $i < $num/2
要慢 10% 以上

Answer 5

应该是一样的，你算法要改改吧，每次都要求平方是不对的，一开始循环那里设置的就直接$sqr=sqrt($num)，然后for的终点为$sqr，效率应该会高很多，试试？

Answer 6

你在开玩笑吧？
在这个算法中 $num 也是变量！

Answer 7

你动态的缩小不如我一开始固定终点，多循环几次都比求平方快，质因子最大不超过$num自身平方，没必要每次都求平方，否则你循环几次就求几次平方，或者是半值

Answer 8

自己写了一遍通过测试
for($i=2;$i<$n/2;$i++){
while(($n%$i)==0){
$n/=$i;
$arr[]=$i;}
}
 $arr[] = $n;
print_r($arr);谢拉 
效率很重要!

Answer 9

这个是不是错了。。  如果起点为$num的平方根，那不是因子全是合数？
比如18，从5开始 那结果就是6和3了？

Answer 10

修改完毕，运行速度由原来的34微秒下降为23微秒
能两端收敛为什么要单边呢？
搜索范围呈几何级数下降，为什么不呢？
function Factorization($num) {
  $end = sqrt($num);
  $k = 1;
  for($i=2; $i<=$end; $i+=$k,$k=2) {
    if(($num % $i) == 0) {
      while( ($num % $i) == 0 ) {
        $num /= $i;
        $r[] = $i;
      }
      $end = sqrt($num);
    }
  }
  if($num > 1) $r[] = $num;
  return join(' * ', $r);
}

Answer 11

function Factorization($num){
for($i=2;$i<=sqrt($num);$i++)
if($num%$i==0){
$num=$num/$i;
echo $i." * ";
$num=Factorization($num);
}
return $num;
}