php最大素因数

Question

我用 PHP 编写了一个程序来查找最大素因数。我认为它非常优化，因为它加载速度非常快。但是，有一个问题：它不计算非常大的数字的质因数。这是程序：

function is_even($s) {      
    $sk_sum = 0;        
    for($i = 1; $i <= $s; $i++) {           
        if($s % $i == 0) { $sk_sum++; }         
    }   
    if($sk_sum == 2) {          
        return true;            
    }          
}

$x = 600851475143; $i = 2; //x is number    
while($i <= $x) {   
    if($x % $i == 0) {
        if(is_even($i)) {
            $sk = $i; $x = $x / $i;
        }
    }
    $i++;   
}
echo $sk;

Answer 1

PHP 中最大的非溢出整数存储在常量 PHP_INT_MAX 中。

您将无法在 PHP 中使用大于此值的整数。

要查看 PHP 的所有预定义常量，只需使用：

<?php
echo '<pre>';
print_r(get_defined_constants());
echo '</pre>';
?>

PHP_INT_MAX 的值可能为 2,147,483,647。

要在 PHP 中处理任意精度的数字，请参阅 GMP 或 BC 数学 PHP 扩展。

Answer 2

您应该阅读有关 Prime 测试 和 筛分。

特别是，您不需要测试每个除数是否为素数。

像下面这样的东西会更快。

while($i <= $x) 
{
    while ($x % $i == 0)
    {
        $sk = $i;
        $x = $x / $i;
    }
    $i++;
}

您还可以在 $i 达到 sqrt($x) 时停止外循环，如果您还没有找到除数，那么您就知道 $x 是质数。

Answer 3

嗯，每种语言都有它自己的（虽然通常是相同的）限制，所以如果你超过了这个 php 的限制，你就不能再更高了。最大整数为 9E18。