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
/**
* 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:
<?php $c = 10000; $m = round((sqrt($c)))+1; $p = array_fill(2, $c-1, 1); $i = 2; while ($i<$m) { $j=$i*2; while($jWhich 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
$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));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 }