«
»

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

This entry was posted by admin on August 12, 2008 at 11:26 pm under PHP. Tagged , , , , . You can leave a response, or trackback from your own site. Follow any responses to this entry through the RSS 2.0 feed.

20 Comments

  1. Niraj says:

    Hey this is awesome. cant believe you actually did this

    August 12, 2008, 11:43 pm

  2. anonymous says:

    nice

    August 13, 2008, 12:04 am

  3. dryu says:

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

    August 21, 2008, 10:08 am

  4. anonymous says:

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

    September 2, 2008, 4:57 am

  6. SvG says:

    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";
    September 17, 2008, 9:13 am

  7. Rune Kaagaard says:

    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.

    December 5, 2008, 5:07 pm

  8. Rune Kaagaard says:

    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

    December 5, 2008, 5:08 pm

  9. Rune Kaagaard says:

    $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));

    December 5, 2008, 5:09 pm

  10. Rune Kaagaard says:

    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));

    December 5, 2008, 5:12 pm

  11. Rune Kaagaard says:

    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));
    December 5, 2008, 5:13 pm

  12. Major Hooters says:

    E=ma^2
    E=mb^2
    E=mc^2!!!!

    December 18, 2008, 11:55 am

  14. Rick Chaides says:

    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

    April 6, 2009, 7:10 pm

  15. Rick Chaides says:

    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;
    }
    }
    ?>

    April 6, 2009, 7:12 pm

  16. RiK0 says:

    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.

    August 26, 2009, 12:15 pm

  17. playfish says:

    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 :)

    March 21, 2010, 12:19 am

  18. Ali says:

    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;
    }

    August 8, 2010, 5:44 pm

  19. Ali says:

    Comment system isn’t great >.<

    Ignore the last $total+3x }

    August 8, 2010, 5:44 pm

  20. admin says:

    <?php

echo "test";
?>
    August 15, 2010, 10:16 pm

Leave a Reply