Foro de elhacker.net

Mi duda es la siguiente:

¿Alguien sabe como hacer para calcular si un nº dado es primo sin necesidad de haberlos almacenado anteriormente?

He estado pensando y lo único que se me ocurre es:
1º) Divide entre 2, si resto != 0;
2º) Divide entre 3, si resto != 0;
3º) Divide entre 5, si resto != 0;
...
...


El problema es que para hacer esto, he tenido que almacenar los primos anteriormente y eso es lo que no quiero.



Saludos!
Espero sus respuestas

La lógica del programa?
Para que almacenar los números?

Partiendo de un número N lo divides por todos los números desde 2 hasta N-1, si en algún momento la división es 0, entonces el número no es primo y sales del bucle, si llega a N-1 y sigue "sobrando" (mod>0) entonces es primo  :P

Saludos

Eso ya lo había pensado. El problema es que para la segunda parte necesito saber qué nº primos hay inferiores a ese.


Saludos!

Bueno lo primero es sencillo, tal como dijo Novlucker pues irías dividiendo entre cada número menor que nuestro número, y si encuentras que ninguno lo divide, pues dirías que es primo.
Para saber los demás números primos inferiores, podrías hacer algo así como un doble bucle, por ejemplo:

$numero = 100;
 
// Bucle 1: Revisamos todos los numeros de 100 a 2
for( $maximo = $numero; $maximo > 2; $maximo--){
   //Bucle 2. Para cada numero, dividimos entre todos los inferiores a el.
   for( $actual = $maximo; $actual > 2; $actual-- ){
     if( $maximo % $actual == 0){
        echo "El numero ($maximo) es un numero primo.<br />";
        break;
     }
   }
}
 

Algo así es lo que se me ocurre ahora.