PHP 找到一个数字的最大素因数

 PHP 常用例子

目标:以有效的方式找到数字的最大素因数。

找到最大素因数是一个非常简单的概念。假设数字是 1092。1092 的所有质因数都是 2, 2, 3, 7, 13。因此，最大的质因数是 13。要找到它，可以使用以下算法:

number = num

步骤1：
如果num可被2整除，则存储最大素因子为2。
继续划分num，直到它不能被2整除。
之后每个分区，将num更新为num/2。
步骤2：
在这一点上，num必须是奇数。
从num的3到平方根开始，如果可分割、分割和更新num以及更新最大素数。
步骤3：
如果修改后的num大于2、用num.更新最大素数。

查找数字的最大质因数

下面的示例说明了上述算法。

<?php
function MaxPrime($num) {
  $CurrMaxPrime = -1;

  //如果$num能被2整除，则存储$CurrMaxPrime
  //为2.继续除$num，直到不能被2整除，每次除完后更新
  //$num 为 $num/2。
  if($num % 2 == 0) {
    $CurrMaxPrime = 2;
    while($num % 2 == 0){
      $num = $num/2;
    }
  }
  
  //此时$num一定是奇数。从3...开始
  //到 $num 的平方根，如果可整除，则除以
  //$num，并更新$CurrMaxPrime
  for($i = 3; $i <= sqrt($num); $i += 2) {
    while($num % $i == 0) {
      $CurrMaxPrime = $i;
      $num = $num/$i;
    }
  }

  //如果修改后的$num大于2，
  //用$num更新$CurrMaxPrime
  if ($num > 2) 
    $CurrMaxPrime = $num;

  return $CurrMaxPrime;
}

$x = 42;
$y = 1092;
$z = 695467363456;

echo "{$x} 最大质因数是: "
     .MaxPrime($x)."\n";
echo "{$y} 最大质因数是: "
     .MaxPrime($y)."\n";
echo "{$z} 最大质因数是: "
     .MaxPrime($z)."\n";
?> 

上面的代码将给出以下输出:

42 最大质因数是: 7
1092 最大质因数是: 13
695467363456 最大质因数是: 5433338777