由网友(无罪释放)分享简介：我需要找到大量的最大素因子：多达12位（XXX，XXX，XXX，XXX）。我已经解决了这个问题，而code适用于小型数字（最多6位）;然而，code不会跑得不够快，不会触发我的服务器超时的东西在100亿元。I need to find the greatest prime factor of a large numb...

我需要找到大量的最大素因子：多达12位（XXX，XXX，XXX，XXX）。我已经解决了这个问题，而code适用于小型数字（最多6位）;然而，code不会跑得不够快，不会触发我的服务器超时的东西在100亿元。

I need to find the greatest prime factor of a large number: up to 12 places (xxx,xxx,xxx,xxx). I have solved the problem, and the code works for small numbers (up to 6 places); however, the code won't run fast enough to not trigger a timeout on my server for something in the 100 billions.

我找到了一个解决方案，感谢所有。

code：

<?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 "nn";
    echo "<b>Answer: </b>". max($prime_factors);    
?>

在这种情况下的测试数是600851475143

The test number in this case is 600851475143.

推荐答案

您code不会找到比大任首相因素的sqrt（N）。要纠正这一点，你必须测试的商 $数量/ $ I 此外，对于发现的每个因素（不仅是首要的因素）。

Your code will not find any prime factors larger than sqrt(n). To correct that, you have to test the quotient $number / $i also, for each factor (not only prime factors) found.

您 is_factor 功能

function is_factor($number, $factor) {
    $half = $number/2;
    for($y=1; $y<=$half; $y++) {
            if(fmod($number, $factor) == 0) {
            return true;
        }
    }
}

就没有意义了。什么是 $ Y 和环路呢？如果 $系数不是一个除数 $号，将执行 $号/ 2 毫无意义的分歧。与固定的，重新排序测试， is_prime_factor 将提供一个良好的加速，因为昂贵的素性测试仅需要对 $数数约数执行。

doesn't make sense. What's $y and the loop for? If $factor is not a divisor of $number, that will perform $number/2 utterly pointless divisions. With that fixed, reordering the tests in is_prime_factor will give a good speedup because the costly primality test needs only be performed for the few divisors of $number.