PHP code is taking very much time in executing when handling large number

Question

This is a simple program to find prime numbers which check for the division of a number at later stage.

I tried to short it by initially taking the integer square root of the number to break down the complexity. But still it is taking very much time in executing the script. What other changes I can implement in my code to decrease the execution time( I already set the max execution time to 5 min)

<?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 Just commented the line for sqrt as this seems to be in correct..but still the loop is taking much time.

Answer 1

One way to improve execution time of your code would be this:

$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>';
    }
}

But there is no need to calculate prime numbers from the begining each time. You can remember every 30 seconds or so where you were, save the result to a database, file, or an array, and then restart the script, which should the continue from where it stopped.