Sieve of Eratosthenes Algorithm

Question

Hi All, I did some searching and was not able to find any information regarding this implementation versus every other one I have seen.

function sieve($top)
{
    for($i = 11; $i<$top; $i+=2)
    {
         if($i % 3 == 0 || $i % 5 == 0 
            ||  $i % 7 == 0)
          {
             continue;
          }
       echo "$i <br />";
   }
}

Yeah I know it just prints it out, but that's not the important part. What is the major pitfall whether it be time or other?

EDIT: Are there any other issues beyond scalability? Also again thanks for the comments about moving forward with prime finding.

Answer 1

The major pitfall of this is it doesn't scale. Once the numbers are large enough anything will be returned. You list of modulus excluders needs to grow with the search.

Answer 2

It's limited to prime numbers up to 11. To extend it any further you need to add || $u % 11 == 0 || $i % 13 == 0 ... etc

Answer 3

You can refer to Sieve of Eratosthenes on Wikipedia; and this link for a PHP implementation.

Answer 4

First, you're only checking against three numbers (3, 7, and 11). For the Sieve of Erathosthenes, you should start with a list of numbers, 2..i. Then loop through that list, and remove numbers that are factors of the number you're iterating on. For example, once you get to 7, which is prime, you'll need to remove 49, 56, and other multiples of 7.

Second, the method I just described would scale very poorly - if you tried looking for primes from 1..10^9, you'd need 10^9 values in your list. There are other ways besides the Sieve of Erathosthenes to find prime numbers - see http://en.wikipedia.org/wiki/Prime%5Fnumber