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.

Answer 2

The best way to reduce this code execution time is by removing it. It's unnecessary to calculate every prime number each time you run this- they are not going to be changing any time soon.

Run it once, write it to a file or database and use that when you need it. I'd personally put it in an array for later use.

Answer 3

Here's the basic algorithm for factoring by trial division; I don't know PHP, so I'll just give pseudocode:

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

There are better ways than that to find the factors of a number, but even that simple method should be sufficient for the Project Euler problem you are trying to solve; you should have a soluion in less than a second. When you're ready for more programming with prime numbers, I modestly recommend this essay at my blog.