我需要找到一个大数的最大质因数:最多 12 位 (xxx,xxx,xxx,xxx)。我已经解决了这个问题,代码适用于小数字(最多 6 个地方);但是,代码运行速度不够快,不会在我的服务器上触发 1000 亿次超时。
我找到了解决方案,感谢大家。
代码:
<?php
set_time_limit(300);
function is_prime($number) {
$sqrtn = intval(sqrt($number));
//won't work for 0-2
for($i=3; $i<=$sqrtn; $i+=2) {
if($number%$i == 0) {
return false;
}
}
return true;
}
$initial = 600851475143;
$prime_factors = array();
for($i=3; $i<=9999; $i++) {
$remainder = fmod($initial, $i);
if($remainder == 0) {
if(is_prime($i)) {
$prime_factors[] = $i;
}
}
}
//print_r($prime_factors);
echo "\n\n";
echo "<b>Answer: </b>". max($prime_factors);
?>
本例测试编号为600851475143。
最佳答案
您的代码不会找到任何大于sqrt(n)
的质因数。要纠正这个问题,您还必须为找到的每个因子(不仅是质因子)测试商 $number/$i
。
您的is_factor
函数
function is_factor($number, $factor) {
$half = $number/2;
for($y=1; $y<=$half; $y++) {
if(fmod($number, $factor) == 0) {
return true;
}
}
}
没有意义。 $y
和循环的作用是什么?如果 $factor
不是 $number
的除数,那将执行 $number/2
完全没有意义的除法。解决了这个问题后,重新排序 is_prime_factor
中的测试将提供很好的加速,因为只需要对 $number
的少数除数执行昂贵的素数测试。
关于php - 计算欧拉计划的主要因素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9370839/