05/03/2006, 11:41
|
| |
| No es un problema tan sencillo como parece.
Creo que lo mejor es generar una lista de primos y actualizarla (ampliarla) cada vez que alguien pregunta por un número mayor que el máximo que tenés.
Esto tiene doble ventaja:
- No tenés que calcularlo todo cada vez
- ya sabés qué números son primos, por lo que tenés que revisar solamente desde tu máximo hasta el número ingresado.
Bueno, de entrada sabés que 1, 2 y 3 son primos, ¿no?
(el cero queda como discutible)
Sea n el número ingresado:
Paso 1º.- se divide entre 2
Si el resto es 0, se pasa al siguiente paso (ya sé que N no es primo)
Si el resto es 1, se divide entre 3 y se vuelve a comprobar el resto.
Así sucesivamente hasta llegar a dividir entre N/2 (o N/2 +1), considerando que estoy buscando solamente números enteros. (N/ (N/2 + 1) ) > 1 y < 2 para todo n
Si ninguna división tiene resto 0, el número es primo.
Paso 2º: Una vez que se llega a la división cuyo resto es 0, se reinicia el proceso, esta vez con (N-1).
(Por supuesto que puede hacerse al revés, partir de 4 hasta N)
Como ves no es un método eficiente (sobretodo para números grandes), por eso te decía lo de guardar una lista.
Creo que con eso es suficiente como para crear el código acorde.
Saludos. |