This is quite fast (but unfortunately memory consuming) algorithm for generating all prime numbers up no n:
$n = 100; //this is the upper limit
for ($i = 2; $i <=$n; $i++){
$primes[] = $i;
}
foreach ($primes as $num){
if ($num != 1){
$step = $num;
for ($i = 2*$num-2; $i <= count($primes); $i= $i + $step){
if ($primes[$i] != 1) {
$primes[$i] = 1;
}
}
}
}
$primes = array_unique($primes);
$primes = array_values($primes);
sort($primes);
unset($primes[0]);
I found this on Wikipedia here. It needs optimization (for example count($primes) doesn’t need to be called on every iteration) but helped me a lot for solving some Project Euler problems.