Расчет основных факторов для проекта Эйлера

Question

Мне нужно найти наибольший простой множитель большого числа: до 12 мест (ххх, ххх, ххх, ххх).Я решил проблему, и код работает для небольших чисел (до 6 мест);однако код не будет работать достаточно быстро, чтобы не вызвать тайм-аут на моем сервере для чего-то из 100 миллиардов.

Я нашел решение, спасибо всем.

Код:

<?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.

Answer 1

Ваш код не найдет каких-либо простых факторов больше 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.

Answer 2

Вот действительно простое и быстрое решение.

LPF(n)
{
    for (i = 2; i <= sqrt(n); i++)
    {
        while (n > i && n % i == 0) n /= i;
    }

    return n;
}