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:

/** * 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<$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>

Hey this is awesome. cant believe you actually did this

nice

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

1st- wrong clear your $i<

2nd- useless

Nice

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

Cool, thx. for sharing that. I wrote this one:

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

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

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

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

Ok…really last try

E=ma^2

E=mb^2

E=mc^2!!!!

[…] Sieve of Eratosthenes in PHP […]

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

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;

}

}

?>

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.

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

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;

}

Comment system isn’t great >.<

Ignore the last $total+3x }

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

I have optimized Ali’s script a bit further: