Eratosthene\'s Sieve

This is a prime number generator developed by Eratosthene\'s in Ancient Greece. Enter a number below and all primes up to that number will be shown.

Maximum number:

'; if ($n != '') { if ($n > 9999) { echo '

Error

Please choose a number less than 10,000.

'; exit; } $n = abs(floor($n)); $primes = array(); // setup large array of integers for ($i = 2; $i <= $n; $i++) { $primes[] = $i; } // loop through array to find and eliminate factors for ($i = 0; $i < count($primes); $i++) { for ($j = 0; $j < count($primes); $j++) { if (($primes[$j] != $primes[$i]) && ($primes[$j] % $primes[$i] == 0)) { // remove $j because it is composite. array_splice($primes, $j, 1); } } } // display results echo '

Results

The prime numbers between 1 and ' , $n , ' are:

' , implode('

', $primes) , '

'; } $t1 = microtime(); $ta = explode(' ', $t0); $tb = explode(' ', $t1); $sec = $tb[1] - $ta[1]; $msec = $tb[0] - $ta[0]; $t = round(($sec + $msec), 3); echo '

Results generated in ' , $t , ' seconds

'; echo ''; ?>