Como encontrar números primos PHP

Les traigo un simple script para encontrar los números primos hasta cierto valor.



El código está comentado para que se entienda.

<?php

//Empezamos a contar el tiempo de ejecución
$time_start = microtime(true); 

function isPrime($num) {
    //1 no es primo. Ver: http://es.wikipedia.org/wiki/N%C3%BAmero_primo
    if($num == 1)
        return false;

    //2 es primo (el único número primo par)
    if($num == 2)
        return true;

    /**
     * Si el número es divisible por dos podemos descartar que sea primo*/
    if($num % 2 == 0) {
        return false;
    }

    /**
     * Chequeamos los números impares. Si alguno es un factor la función retorna falso.
     */
    for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
        if($num % $i == 0)
            return false;
    }

    return true;
}


//La variable max es el número mas alto a buscar
$max = 1000000;
for ($i=0; $i < $max ; $i++) { 
$test = isPrime($i);
if ($test == 1) {
$primos[] = $i;
}
}
/*Imprimimos los resultados incluyendo el tiempo de ejecución
Los resultados se muestran de la forma orden de resultado -> valor
*/
echo "<h2>Se buscaron números primos hasta el ".number_format($max,0,",",".")."<br>";
echo "Se encontraron ".number_format(count($primos),0,",",".")." números primos</h2> <br>";
//execution time of the script
$time_end = microtime(true);

///Dividimos por 60 para obtener el tiempo en minutos
echo '<b><h3>Tiempo de ejecución:</b> '.($time_end - $time_start).' segundos'."</h3><br>";
echo "<br>";
foreach ($primos as $key => $value) {
echo ($key+1)." -> ".number_format($value,0,",",".")."<br>";
}

El resultado es algo así:

Se buscaron números primos hasta el 100
Se encontraron 25 números primos

Tiempo de ejecución: 0.00018191337585449 segundos

1 -> 2
2 -> 3
3 -> 5
4 -> 7
5 -> 11
6 -> 13
7 -> 17
8 -> 19
9 -> 23
10 -> 29
11 -> 31
12 -> 37
13 -> 41
14 -> 43
15 -> 47
16 -> 53
17 -> 59
18 -> 61
19 -> 67
20 -> 71
21 -> 73
22 -> 79
23 -> 83
24 -> 89
25 -> 97