Aug 122008
 

Prime Numbers: Positive natural numbers which has exactly two distinct natural number divisors 1 and itself.

Sieve Of Eratosthenes is a computer algorithm to find out prime numbers upto a specified integer starting from 2.
The time complexity of a unfaithful sieve is Θ(n2/(log n)2) ( regardless of what wikipedia might say :( )

I tried the program in PhP ( for all the php enthusiast :) ). There is a cool animation ( I found ) for proper understanding:

Sieve of Eratosthenes in PHP

Sieve of Eratosthenes in PHP

/**
* Nishchay Shah                    August 10 2008
*
* Program: To find prime numbers
* Algorithm: Sieve of Eratosthenes
*
* Memory And Time Cost:
*        09552  bytes for 20 numbers        ( 250 to 380 usec )
*        49920 bytes for 100 numbers        ( 1600 to 2500 usec )
*        114.1 K bytes for 500 numbers    ( 230 to 350 msec )
*
*
*/
echo"
<pre>;"; // for browser output
$max = 10;   // find prime numbers till this value. [ Change it for the higher limit. Please dont go crazy.]

/// Populate the scan array
for($i=2;$i&lt;$max;$i++){
$scan[]= $i;
}
/// Call the function
primeNumber($scan);

/// Function to find prime numbers
function primeNumber($scan){
$tempFound = array(); // declare array,save memory
global $primeNumbers;
$number = current($scan); // current data pointer

foreach($scan as $remainingNumber) {
if(!fmod($remainingNumber,$number)){
$tempFound[] = $remainingNumber; //make list of multiples
} // end of if mod = 0
} // end foreach

$scan = array_diff($scan, $tempFound);     // remove the multiples from the list
$primeNumbers[] =  current($scan);
if(count($scan) !=1){
primeNumber($scan);
} // end if count is not 1
else{
return;
}
} // end of function primeNumber

/// Add 2 in the beginning ..
$primeNumbers = array_pad($primeNumbers, -(count($primeNumbers)+2), 0);
$primeNumbers= array(2) + $primeNumbers;
/// Output
print_r($primeNumbers);</pre>
  • Share/Bookmark

  22 Responses to “Sieve of Eratosthenes in PhP”

  1. Hey this is awesome. cant believe you actually did this

  2. nice

  3. Please, correct the loop condition at line 19. Your entity was converted to HTML form.

  4. 1st- wrong clear your $i&lt
    2nd- useless

  5. You could also try the following which I created a bit earlier today:

    //Set maximum number
    $maxprime = 100;
     
    //Set all numbers to 1
    for ($a = 0; $a &lt;= $maxprime; $a++)
    	$primes[$a] = 1;
     
    //Do not include 0 and 1
    $primes[0] = 0;
    $primes[1] = 0;
     
    //Search for primenumbers
    for ($a = 2; $a * $a &lt; $maxprime; $a++)
    	if ($primes[$a] == 1)
    		for ($b = $a * $a; $b &lt;= $maxprime; $b += $a)
    			$primes[$b] = 0; //Remove the none primes
     
    //Display the primenumbers
    for ($c = 0; $c &lt;= $maxprime; $c++)
    	if ($primes[$c] == 1)
    		echo $c ."\n";
  6. Cool, thx. for sharing that. I wrote this one:

    <?php
    $c = 10000;
    $m = round((sqrt($c)))+1;
    $p = array_fill(2, $c-1, 1);
    $i = 2;
    while ($i<$m) {
    	$j=$i*2;
    	while($j
    

    Which displays all primes until 50000 in 0.552s seconds, compared to 3m39.183s for the script in this article.

  7. Hmm cropped my code. Trying again:

    <?php
    $c = 50000;
    $m = (int)((sqrt($c))+1);
    $p = array_fill(2, $c-1, 1);
    $i = 2;
    while ($i<$m) {
    $j=$i*2;
    while($j

  8. $c = 50000;
    $m = (int)((sqrt($c))+1);
    $p = array_fill(2, $c-1, 1);
    $i = 2;
    while ($i<$m) {
    $j=$i*2;
    while($j<$c+1) {
    $p[$j] = 0;
    $j += $i;
    }
    $i++;
    }
    echo implode(‘ ‘,array_keys($p, 1));

  9. zzz. Sorry about that. Last try:

    $c = 50000;
    $m = (int)((sqrt($c))+1);
    $p = array_fill(2, $c-1, 1);
    $i = 2;
    while ($i<$m) {
    $j=$i*2;
    while($j<$c+1) {
    $p[$j] = 0;
    $j += $i;
    }
    $i++;
    }
    echo implode(‘ ‘,array_keys($p, 1));

  10. Ok…really last try :(

    $c = 50000;
    $m = (int)((sqrt($c))+1);
    $p = array_fill(2, $c-1, 1);
    $i = 2;
    while ($i<$m) {
        $j=$i*2;
        while($j<$c+1) {
            $p[$j] = 0;
            $j += $i;
        }
        $i++;
    }
    echo implode(' ',array_keys($p, 1));
    
  11. E=ma^2
    E=mb^2
    E=mc^2!!!!

  12. Here’s my attempt at this. I think it’s the fastest one yet!

    <?php
    $prime_array = array_fill(2, $count-1, 1);
    for($i = 2; $i < $count; $i++) {
    if(!isset($prime_array[$i])) continue;
    $j = $i * $i;
    while($j

  13. Attempt number two. I wish there was instructions for commenting. :-)

    <?php
    $prime_array = array_fill(2, $count-1, 1);
    for($i = 2; $i < $count; $i++) {
    if(!isset($prime_array[$i])) continue;
    $j = $i * $i;
    while($j <= $count) {
    unset($prime_array[$j]);
    $j += $i;
    }
    }
    ?>

  14. This is not the Sieve of Eratosthenes.
    This is a variation on the classical trial division algorithm.
    That is the reason why this is so slow, it does more computation *and*
    uses modulo instead of simple addition.

  15. i was beginning to feel i may end up being the only woman / man which thought about this, at the very least currently i realize i’m not loco :) i am going to be sure to take a look at some other posts just after i get some caffeine in me, it can be stressful to read with out my coffee, I was up late last night jamming facebook poker and after downing a few ales i ended up giving up all my zynga poker chips take care :)

  16. I gave this a go, finds all primes < 1million in ~0.44s

    function CountPrimes($max) {
    $vals = Array();
    $total = 1;
    for($i=3; $i<$max; $i += 2) {
    if(!isset($vals[$i])) {
    $total++;
    $l = 2*$i;
    for($j = $i*$i; $j < $max; $j += $l) {
    $vals[$j] = true;
    }
    }
    }
    return $total;
    }

    }
    }
    return $total;
    }

  17. Comment system isn’t great >.<

    Ignore the last $total+3x }

  18. <?php
    
    echo "test";
    ?>
    
  19. <?php

    $numbers = array();
    $limit = 100000;
    for ($i = 1 ; $i <= $limit; $i++) {
    $numbers[$i] = $i;
    }

    do {
    $index = key($numbers);
    $value = $numbers[$index];
    if ($value == 0 || $value == 1) continue;
    for ($p = $value; $p

  20. I have optimized Ali’s script a bit further:

        //Primes until 10 million
        $max       = intval(pow(10, 7));
        $notPrimes = Array();
        $primes    = array(2, 3);
        $i         = 3;
        while ($i &lt;= $max) {
            $j = $i + 4;
            for ($i += 2; $i &lt;= $j; $i += 2) {
                if (!isset($notPrimes[$i])) {
                    $primes[] = $i;
                    $step     = 2 * $i;
                    for ($k = $i * $i; $k &lt; $max; $k += $step) {
                        $notPrimes[$k] = true;
                    }
                }
            }
        }
     
        echo implode($primes, &#039; &#039;);

 Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="">