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

[amadeo123]

Buenas. Estoy preparándome unos ejercicios para enseñar php a gente nivel cero.

Estaba haciendo el mítico ejercicio de sacar números primos y se me ha ocurrido esto.

Código PHP:

  <?php
          
           $x = 100;
           
           for ( $i=1; $i <=$x ; $i++){
                $restos =0;
                for ( $a=1; $a <=$i ; $a++){
                    if ($i % $a == 0)
                        $restos++;
                        if ($restos >=3)
                            break;
                            
                }
                if($restos <=2 ){
                    echo "<br>";
                    echo $i ." es numero primo.";
                }    
           }
           
        
        ?>   

La solución es correcta, pero me ha picado el gusanillo ya que recuerdo hace años que mi profesor dio una solución con un único bucle for.

Por simple curiosidad. Se os ocurre una solución más optimizada ?

[mauritosuarez]

Hola amadeo123, prueba con este.

Código PHP:

<?php
$valor = 20;
$primo = 0;
 
for ($b = 1; $b < $valor; $b++) {
    if ($valor % $b == 0) {
        $primo++;
    }
}
 
if ($primo >= 2) {
    echo "No es primo";
} else {
    echo "Es primo";
}
 
?>
 

Espero te sirva.

Saludos.

[amadeo123]

Gracias ... tu respuesta no es lo que buscaba, pero me ha servido para darme cuenta de una cosa. El ejercicio que recordaba con un solo for es como tu lo has planteado, decir si es numero primo o no, no sacar todos los primos.

En tal caso deduzco que es imposible implementar un ejemplo como el mio sin usar dos bucles.

[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