Improve performance of php on local server

Question

I have a XAMPP install, with pretty much the default config.

Performance isn't much of a problem in general as I use PHP mostly to run web pages and small web apps. Waiting a couple seconds for a page is not unusual.

However, I have recently taken up the problems from Project Euler and decided to do them in PHP.

Try as I may, I couldn't get my code to run in less than 1 minute 1 second (optimized down from almost 3 min) and I was getting pretty embarrassed, especially considering most posters on Pjt Euler reported times of 1-3 seconds. (#7, find the 10001th prime)

I ported my code to C#, and the same task completed in a blink. 0.4 seconds. Same algorithm, the only notable difference in the code is that I used a List in C# to replace the array I was using in PHP.

While I did expect C# to outperform php, this difference leads me to suspect a gross configuration problem, but I have no idea where to look.

What could be the cause of this poor performance?

---

Edit: Here is the code:

In PHP:

/*
  * Project Euler #7:
  * By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
  * What is the 10001st prime number?
  */

ini_set('max_execution_time', 300);  
echo "start time:" . date("i:s:u") . "<br />";
function isPrime($number, $prevPrimes)
{       
    foreach ($prevPrimes as $key =>$prime)
    {
        if ($prime == 1)
        {
            continue;
        }
        elseif ($number % $prime == 0)
        {
            return 0;
        }
    }
    // If we get to here, $number is prime
    return $number; 
}
$primes = array();
$i = 0;
$nbPrimes = 0;
while ($nbPrimes <10001)
{
    $i++;
    if ($i % 2 != 0)
    {
        $result = isPrime($i, $primes);

        if ($result != 0)
        {
            $primes[] = $i;
            $nbPrimes++;
        }
    }
}
echo "#$nbPrimes: $result<br>";

echo "End time:" . date("i:s:u") . "<br />";

In C#:

public static void RunSnippet()
{
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();

    List<int> primes = new List<int>();
    int i = 0;
    int nbPrimes = 0;
    int result =0;
    while (nbPrimes <10001)
    {
        i++;
        if (i % 2 != 0)
        {
            result = isPrime(i, primes);

            if (result != 0)
            {
                primes.Add(i);
                nbPrimes++;
            }
        }
    }
    stopwatch.Stop();
    Console.WriteLine("Time elapsed: {0}",
    stopwatch.Elapsed);
    Console.WriteLine ("#" + nbPrimes + ": " + result.ToString());
}
public static int isPrime(int number, List<int> prevPrimes)
{
    foreach (int prime in prevPrimes)
    {
        if (prime == 1)
        {
            continue;
        }
        else if (number % prime == 0)
        {
            return 0;
        }
    }
    // If we get to here, number is prime
    return number;  
}   

Answer 1

"Use the force ..." of math! Just throwing some code pointless. Here are just a few points that can boost the performance.

• why you are using array to match the number against?

• the foreach function is thus ineffective - the cycle should end at floor(sqrt(number))

  example: sqrt(64) = 8 -> all prime dividers will be from 1 to 8. The others will be product of them( 32 = 4 x 8 = 2x2x2x2x2 )

• use formulas to jump to the next possibly prime number

  math:

  numbers divisable by 2 - 2, 4, 6, 8, 10, 12 -> 2k+1 = 2x1+1 = 3, 5, .....

  numbers divisable by 3 - 3, 6, 9, 12 -> we already have 6 and 12, so 3, 9, 15, 21 -> 3(2k-1) = 3(2x1-1) = 3, 9, ...

here is some pseudo code from hk admin at project euler

isPrime ( number )
{
    if ( number == 1 )      return false
    elseif ( number < 4 )       return true
    elseif ( number % 2 == 0 )  return false
    elseif ( number < 9 )       return true
    elseif ( number % 3 == 0 )  return false
    else
        r = floor ( sqrt ( number ) ) 
    f = 5
    while ( f <= r )
    {
        if ( number % f == 0 ) return false
        if ( number % ( f + 2 ) == 0 ) return false
        f = f + 6
    }
    return true
}

PS

About the difference in the speed of the execution - PHP is interpreted language, to view the result in browser you have 3 programs running - browser, server, php interpreter. You make a http request, the server calls php (and probably a bunch of other stuff, logging for example),php reads the script and executes it. There are much more steps than in C#.

In C# the compiled code is executed.