Foros del Web » Programando para Internet » PHP »

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

Estas en el tema de Se os ocurre un algoritmo de números primos más eficiente que este ? en el foro de PHP en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 22/01/2015, 05:40
 
Fecha de Ingreso: diciembre-2011
Mensajes: 134
Antigüedad: 12 años, 6 meses
Puntos: 5
Se os ocurre un algoritmo de números primos más eficiente que este ?

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 <=){
                    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 ?
  #2 (permalink)  
Antiguo 22/01/2015, 05:56
 
Fecha de Ingreso: octubre-2014
Ubicación: Buenos Aires
Mensajes: 278
Antigüedad: 9 años, 9 meses
Puntos: 12
Respuesta: Se os ocurre un algoritmo de números primos más eficiente que este ?

Hola amadeo123, prueba con este.

Código PHP:
Ver original
  1. <?php
  2. $valor = 20;
  3. $primo = 0;
  4.  
  5. for ($b = 1; $b < $valor; $b++) {
  6.     if ($valor % $b == 0) {
  7.         $primo++;
  8.     }
  9. }
  10.  
  11. if ($primo >= 2) {
  12.     echo "No es primo";
  13. } else {
  14.     echo "Es primo";
  15. }
  16.  
  17. ?>

Espero te sirva.

Saludos.
__________________
http://www.sp-vision.net
  #3 (permalink)  
Antiguo 22/01/2015, 08:46
 
Fecha de Ingreso: diciembre-2011
Mensajes: 134
Antigüedad: 12 años, 6 meses
Puntos: 5
Respuesta: Se os ocurre un algoritmo de números primos más eficiente que este ?

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.
  #4 (permalink)  
Antiguo 22/01/2015, 10:35
Avatar de hhs
hhs
Colaborador
 
Fecha de Ingreso: junio-2013
Ubicación: México
Mensajes: 2.995
Antigüedad: 11 años
Puntos: 379
Respuesta: Se os ocurre un algoritmo de números primos más eficiente que este ?

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:
Ver original
  1. $time = microtime(TRUE);
  2.  
  3. function isPrime($number) {
  4.     $i = 2;
  5.  
  6.     if ($number == 2) {
  7.         return true;
  8.     }
  9.  
  10.     while ($i <= sqrt($number)) {
  11.         if ($number % $i == 0) {
  12.             return false;
  13.         }
  14.         $i++;
  15.     }
  16.  
  17.     return true;
  18. }
  19.  
  20. for($i = 0; $i <= 10000; $i++)
  21. {
  22.     if(isPrime($i)){
  23.           echo "{$i} es numero primo <br>";
  24.     }
  25. }
  26.  
  27. //Tiempo estimado de ejecución
  28.  
  29.     'memory' => (memory_get_usage() - $mem) / (1024 * 1024),
  30.  
  31.     'seconds' => microtime(TRUE) - $time
  32.  
  33. ));
Si lo comparas contra tu algoritmo, notaras que para un rango de 10000 números tu aproximación tarda mucho mas
__________________
Saludos
About me
Laraveles
A class should have only one reason to change.

Etiquetas: eficiente, primos
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 06:25.