prime generator optimization

Question

I'm starting out my expedition into Project Euler. And as many others I've figured I need to make a prime number generator. Problem is: PHP doesn't like big numbers. If I use the standard Sieve of Eratosthenes function, and set the limit to 2 million, it will crash. It doesn't like creating arrays of that size. Understandable.

So now I'm trying to optimize it. One way, I found, was to instead of creating an array with 2 million variable, I only need 1 million (only odd numbers can be prime numbers). But now it's crashing because it exceeds the maximum execution time...

function getPrimes($limit) {
$count = 0;
for ($i = 3; $i < $limit; $i += 2) {
    $primes[$count++] = $i;
}

for ($n = 3; $n < $limit; $n += 2) {
    //array will be half the size of $limit
    for ($i = 1; $i < $limit/2; $i++) {
        if ($primes[$i] % $n === 0 && $primes[$i] !== $n) {
            $primes[$i] = 0;
        }
    }
}

return $primes;
}

The function works, but as I said, it's a bit slow...any suggestions?

One thing I've found to make it a bit faster is to switch the loop around.

foreach ($primes as $value) {
    //$limitSq is the sqrt of the limit, as that is as high as I have to go
    for ($n = 3; $n = $limitSq; $n += 2) {
        if ($value !== $n && $value % $n === 0) {
            $primes[$count] = 0;
            $n = $limitSq; //breaking the inner loop
        }
    }
    $count++;
}

And in addition setting the time and memory limit (thanks Greg), I've finally managed to get an answer. phjew.

Answer 1

Without knowing much about the algorithm:

1. You're recalculating $limit/2 each time around the $i loop
2. Your if statement will be evaluated in order, so think about (or test) whether it would be faster to test $primes[$i] !== $n first.

Side note, you can use set_time_limit() to give it longer to run and give it more memory using

ini_set('memory_limit', '128M');

Assuming your setup allows this, of course - on a shared host you may be restricted.

Answer 2

From Algorithmist's proposed solution

This is a modification of the standard Sieve of Eratosthenes. It would be highly inefficient, using up far too much memory and time, to run the standard sieve all the way up to n. However, no composite number less than or equal to n will have a factor greater than sqrt{n}, so we only need to know all primes up to this limit, which is no greater than 31622 (square root of 10^9). This is accomplished with a sieve. Then, for each query, we sieve through only the range given, using our pre-computed table of primes to eliminate composite numbers.

This problem has also appeared on UVA's and Sphere's online judges. Here's how it's enunciated on Sphere.