Se os ocurre un algoritmo de números primos más eficiente que este ?

[hhs]

En realidad la comprobación se hace en un solo for, pero para buscar en un rango de numeros vas a necesitar otro for o foreach dependiendo el caso.
La optimización no siempre involucra menos código como se piensa. Te voy a dejar otro aproximación que es mas eficiente que la .

Código PHP:

$time = microtime(TRUE);
$mem = memory_get_usage();
 
function isPrime($number) {
    $i = 2;
 
    if ($number == 2) {
        return true;
    }
 
    while ($i <= sqrt($number)) {
        if ($number % $i == 0) {
            return false;
        }
        $i++;
    }
 
    return true;
}
 
for($i = 0; $i <= 10000; $i++)
{
    if(isPrime($i)){
          echo "{$i} es numero primo <br>";
    }
}
 
//Tiempo estimado de ejecución
print_r(array(
 
    'memory' => (memory_get_usage() - $mem) / (1024 * 1024),
 
    'seconds' => microtime(TRUE) - $time
 
));
 

Si lo comparas contra tu algoritmo, notaras que para un rango de 10000 números tu aproximación tarda mucho mas