Calcular si un nº dado es primo

Iniciado por luiggy2, 10 Marzo 2009, 16:54 PM

0 Miembros y 1 Visitante están viendo este tema.

luiggy2

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
" Las grandes ideas suelen salir la mayoría de veces de grandes estupideces "

Novlucker

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
Contribuye con la limpieza del foro, reporta los "casos perdidos" a un MOD XD

"Hay dos cosas infinitas: el Universo y la estupidez  humana. Y de la primera no estoy muy seguro."
Albert Einstein

luiggy2

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


Saludos!
" Las grandes ideas suelen salir la mayoría de veces de grandes estupideces "

Agente Naranja

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:

Código (php) [Seleccionar]
$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.