SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: alex_loko666 en Miércoles 28 de Septiembre de 2005, 08:36
-
soy principiante en esto de programacion nececito ayuda con lo sig.
un algoritmo para determinar si un numero es primo o no
:devil:
-
Hola
Un numero primo es aquel que solo es divisible (con resto cero o completamente) por el mismo o por 1.
Por tanto lo mejor es que uses la operacion % y busques con un bucle for desde n-1 hasta 2 para ver si es divisible completamente por otros numeros, ental caso no seria un numero primo
salu2 :hola:
-
Exactamente, pero incluso podrías comprobar si no es divisible por un I que varía desde 2 hasta SQRT(num) (redondeado hacia abajo).
Existe una prueba matemática que demuestra que si un número no es divisible por ningún entero hasta su raíz cuadrada redondeada hacia abajo, no será divisible por ningún otro. (Pero sinceramente no recuerdo la demostración :S)
Y para qué hacerlo así? Te daría muchísima velocidad en el programa.
Saludos.
-
Hola que tal.
El metodo mas eficiente para hacer una prueba de primacia o primalidad es usando el algoritmo de Miller-Rabin, supongo que este es al que se refiere Alpha_ ya que este es obtenido a partir de algunas demostraciones matemáticas.
Sólo búsca en google: Miller Rabin primality test y encontraras el algoritmo en muchas páginas, la ventaja de este algoritmo es que es muy rápido y puedes hacer pruebas con numeros gandes, yo lo probe con numeros de hasta 1024 bits y me respondia en menos de 2 segundos, ya no lo probe con números más grandes pero también debe dar respuestas rápidas, ya que este algoritmo es usado por grandes aplicaciones matemáticas como maple.
Bueno, espero encuentres fácil de implementar el código y si tienes algunas dudas puedes preguntar.
Hasta luego.