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

You can use a bit field to store your sieve. That is, it's roughly identical to an array of booleans, except you pack your booleans into a large integer. For instance if you had 8-bit integers you would store 8 bits (booleans) per integer which would further reduce your space requirements.

Additionally, using a bit field allows the possibility of using bit masks to perform your sieve operation. For example, if your sieve kept all numbers (not just odd ones), you could construct a bit mask of b01010101 which you could then AND against every element in your array. For threes you could use three integers as the mask: b00100100 b10010010 b01001001.

Finally, you do not need to check numbers that are lower than $n, in fact you don't need to check for numbers less than $n*$n-1.

Answer 3

Once you know the number is not a prime, I would exit the enter loop. I don't know php, but you need a statement like a break in C or a last in Perl.

If that is not available, I would set a flag and use it to exit the inter loop as a condition of continuing the interloop. This should speed up your execution as you are not checking $limit/2 items if it is not a prime.

Answer 4

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.

Answer 5

if you want speed, don’t use PHP on this one :P

no, seriously, i really like PHP and it’s a cool language, but it’s not suited at all for such algorithms