Код PHP занимает очень много времени при обработке большого количества

Это простая программа для поиска простых чисел, которая проверяет деление числа на более позднем этапе.

Я попытался сократить его, сначала взяв целочисленный квадратный корень из числа, чтобы разбить сложность. Но все же выполнение скрипта занимает очень много времени. Какие еще изменения я могу внести в свой код, чтобы уменьшить время выполнения (я уже установил максимальное время выполнения на 5 минут)

<?php
error_reporting(E_ALL);
$num = 600851475143;
//$sqrt_num = (int)sqrt($num);

for( $j = 2; $j <= $num; $j++ )
{
    for( $k = 2; $k < $j; $k++ )
    {
        if( $j % $k == 0 )
        {
        break;
        }

    }
    if( $k == $j )
    {
        //echo "Prime Number : ", $j, "<br>";
        if( $num % $j == 0 )
        {
        echo "Prime number : ", $j, "<br>";
        }
    }
}

EDIT Только что прокомментировал строку для sqrt, так как она кажется правильной... но цикл все равно занимает много времени.


php for-loop execution prime-factoring largenumber
person swapnesh    schedule 03.03.2013    source источник
comment
Насколько большими могут быть числа? Я буду застрелен всеми, у кого есть какое-то чувство хорошего кода здесь, но если он имеет ограниченный размер, может быть быстрее просто кэшировать первые пару тысяч простых чисел, а не вычислять их каждый раз. И поскольку они не меняются, вам действительно не нужно вычислять их в первый раз, поэтому вместо кеша читайте хардкод.   -  person Nanne    schedule 03.03.2013
comment
@Nanne, ты имеешь в виду, что я сначала поместил их все в массив, а затем применил деление к числу? Пожалуйста, уточните это немного больше   -  person swapnesh    schedule 03.03.2013
comment
@swapnesh дивизия? нет. Я имел в виду, что вы поместили ВСЕ простые числа в массив. Тогда у вас есть массив простых чисел, которые вы можете повторить, как вы делаете здесь. нет необходимости делать расчеты. Но было бы полезно узнать, в чем заключается настоящая проблема, которую вам нужно исправить?   -  person Nanne    schedule 03.03.2013
comment
@Nanne с этим кодом мой браузер зависает ... однако он отлично работает при предоставлении небольших чисел   -  person swapnesh    schedule 03.03.2013
comment
@MarkoD, почему ты так подумал? хотя я знаю, что ты не ответил мне   -  person swapnesh    schedule 03.03.2013
comment
@MarkoD, лол, это не такой случай, братан. На самом деле я все еще смотрю в код, чтобы заставить его работать, так что, может быть, я пропустил какое-то действие здесь ... но на самом деле это не случай невежества :)   -  person swapnesh    schedule 03.03.2013
comment
@MarkoD, не могли бы вы просто опубликовать ответ ... так как на этот раз я не в своем уме, лол   -  person swapnesh    schedule 03.03.2013
comment
@MarkoD Я только что проверил, и размещение sqrt не будет правильным методом для использования здесь. ставлю 2 в этом случае   -  person swapnesh    schedule 03.03.2013
comment
вместо for( $k = 2; $k < $j; $k++ ) напишите $cond = sqrt($j); for( $k = 2; $k <= $cond; $k++ ) и вместо if( $k == $j ) напишите if( $k > $cond ). И снимите if( $num % $j == 0 ) чек. Я тестировал, и это работает. Я удалю свои предыдущие комментарии, так как они сейчас не нужны   -  person Marko D    schedule 03.03.2013
comment
@MarkoD Просто вставь это как ответ, и я отчаянно хочу его принять .. большое спасибо, братан :)   -  person swapnesh    schedule 03.03.2013

Ответы (3)


arrow_upward
2
arrow_downward

Один из способов улучшить время выполнения вашего кода:

$num = 1000;

for($j = 2; $j <= $num; $j++)
{
    $cond = sqrt($j);
    for($k = 2; $k <= $cond; $k++)
    {
        if($j % $k == 0)
        {
        break;
        }

    }
    if($k > $cond)
    {
        echo 'Prime number: ' . $j . '<br>';
    }
}

Но нет необходимости каждый раз вычислять простые числа сначала. Вы можете каждые 30 секунд или около того вспоминать, где вы были, сохранять результат в базе данных, файле или массиве, а затем перезапускать скрипт, который должен продолжаться с того места, где он остановился.

person Marko D    schedule 03.03.2013
comment
Чтобы еще больше сократить время выполнения: обработайте 2 перед циклом, затем сосчитайте от 3 до 2 в обоих циклах. - person Terje D.; 03.03.2013

arrow_upward
2
arrow_downward

Лучший способ сократить время выполнения этого кода — удалить его. Нет необходимости вычислять каждое простое число каждый раз, когда вы запускаете это — они не изменятся в ближайшее время.

Запустите его один раз, запишите в файл или базу данных и используйте, когда вам это нужно. Я бы лично поместил его в массив для последующего использования.

person chip    schedule 03.03.2013
comment
Я указал, что это массив, и все же его время истекает для меньшего числа.. проверьте codepad.org/bJUjoom6 - person swapnesh; 03.03.2013

arrow_upward
1
arrow_downward

Вот основной алгоритм разложения на множители пробным делением; Я не знаю PHP, поэтому просто приведу псевдокод:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        while n % f == 0
            append f to fs
            n := n / f
        f := f + 1
    if n > 1 append n to fs
    return fs

Есть лучшие способы найти множители числа, но даже этого простого метода должно быть достаточно для задачи проекта Эйлера, которую вы пытаетесь решить; у вас должно быть решение менее чем за секунду. Когда вы будете готовы к дальнейшему программированию с простыми числами, я скромно рекомендую это эссе в моем блоге.

person user448810    schedule 03.03.2013
comment
большое спасибо за псевдокод ... это действительно поможет мне лучше понять концепцию программирования ... и спасибо за ссылку, а также +1 за обмен знаниями :) - person swapnesh; 03.03.2013