使用php的最大素因子

我在PHP中编写了一个程序来查找最大的素数因子。我认为它是非常优化的，因为它的加载速度非常快。但是，存在一个问题：它不能计算非常大数量的主要因素。下面是程序：使用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;

来源

2010-05-19 good_evening

我将'is_even'重命名为'is_prime'，并让它在函数的最后一行返回false。此外，您不必在该循环中包含$ i = 1或$ i = $ s，如果可以用任何其他数字进行分割，则可以返回false。 – catchmeifyoutry 2010-05-19 18:32:31

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 Math PHP扩展。

来源

2010-05-19 18:32:19 Dolph

好，每一种语言都有它自己（而通常相同）的限制，所以如果你超过这个PHP的限制，你不能得到任何更高。 Max Integer是9E18。

来源

2010-05-19 18:30:40

当然，您可以扩展这些限制，只需编写一个类（或找到一个库），该类将任意大数存储为小于MAX_INT的数组数组，并提供标准运算符来处理它们。 – tloach 2010-05-19 18:35:44

请参阅我的回答，以获取GMP和BC Math扩展的链接，这些扩展可以在PHP中处理任意大的数字。 – Dolph 2010-05-19 18:41:22

你的建议是一个很好的解决方法。但是，你不能超过给定的限制。 – 2010-05-20 06:54:54

您应该阅读约Prime testing和Sieving。

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

像下面这样会更快。

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

您也可以停止你的外循环时，$ i达到的sqrt（$ X），如果你还没有找到一个除数又那么你知道$ x是素数。

来源

2010-05-19 18:30:51 David

使用php的最大素因子

回答

相关问题