Question

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.

Was it helpful?

Solution

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.

OTHER TIPS

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

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

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_number

This function use "Sieve of Eratosthenes Algorithm"

function getPrimaryNumbers($n)
{
    $sieve = [];
    for($i = 1; $i <= $n; $i++) {
        $sieve[$i] = $i;
    } 

    $i =2;
    while($i * $i <= $n) {      
        if(isset($sieve[$i])) {
            $k = $i;
            while ($k * $i <= $n) {         
                unset($sieve[$k * $i]);
                $k++;
            }   
        }
    $i++;
    }           
    return $sieve;
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top