Test números primos
Publicado: 23 Nov 2009, 12:44
Este más que un programa completo es un estudio sobre posibles funciones para comprobar la primalidad de números enteros.
Al principio del script hay un par de códigos para probar las funciones, tal como está se ejecutará el primero (ver si un número es primo) y finalizará. Para probar el segundo (comprobar un rango) o se comenta el primero o se quita el Exit.
Como digo lo importante no es el programa en sí, sino las funciones que vienen después, es más bien una ayuda a programadores.
No se ha implementado las más evidentes, como buscar divisores entre todos los enteros menores que el número dado, ni siquiera mirar entre los impares menor que la raíz cuadrada del número. Se han buscado métodos más eficientes que estos (normalmente derivados de ellos).
La conclusión del estudio fue "AutoiT no es el lenguaje más adecuado para esto", pero si hace falta y programarlo en otro lenguaje no es opción, aquí está mi aportación.
En el fuente hay más detalles de las funciones implementadas, recomiendo ampliar allí la información, el resumen es este:
_EsPrimo3: busca divisores ignorando pares y divisibles entre 3
_EsPrimo3V: el anterior pero buscando inicialmente en un vector fijo de primos para acelerar
_EsPrimo5: como _EsPrimo3 pero también discriminando múltiplos de 5
_EsPrimo7V: ... y los de 7, utilizando un vector para hacer elegante el código
_EsPrimo7: Este es el código "feo" del anterior, sin usar el vector. Es el más rápido de todos.
_MR: Test de Miller-Rabin, método probabilístico estupendo para números gigantescos, pero para pequeños no es tan interesante. Básicamente se ha traducido esta versión http://en.literateprograms.org/Miller-R ... %28Java%29
Este último método es un test que dice si el número es primo o no, las demás funciones además devuelven en @extended el divisor mínimo cuando el número es compuesto. El test de Miller-Rabin es infalible para números compuestos. Cuando el número es primo hay una pequeña probabilidad de fallo. Esta probabilidad es acotable, por ejemplo yo ejecuto el test 20 veces, lo que da una probabilidad de acierto del 99,99999999990905% ,que es bastante alta
Al principio del script hay un par de códigos para probar las funciones, tal como está se ejecutará el primero (ver si un número es primo) y finalizará. Para probar el segundo (comprobar un rango) o se comenta el primero o se quita el Exit.
Como digo lo importante no es el programa en sí, sino las funciones que vienen después, es más bien una ayuda a programadores.
No se ha implementado las más evidentes, como buscar divisores entre todos los enteros menores que el número dado, ni siquiera mirar entre los impares menor que la raíz cuadrada del número. Se han buscado métodos más eficientes que estos (normalmente derivados de ellos).
La conclusión del estudio fue "AutoiT no es el lenguaje más adecuado para esto", pero si hace falta y programarlo en otro lenguaje no es opción, aquí está mi aportación.
En el fuente hay más detalles de las funciones implementadas, recomiendo ampliar allí la información, el resumen es este:
_EsPrimo3: busca divisores ignorando pares y divisibles entre 3
_EsPrimo3V: el anterior pero buscando inicialmente en un vector fijo de primos para acelerar
_EsPrimo5: como _EsPrimo3 pero también discriminando múltiplos de 5
_EsPrimo7V: ... y los de 7, utilizando un vector para hacer elegante el código
_EsPrimo7: Este es el código "feo" del anterior, sin usar el vector. Es el más rápido de todos.
_MR: Test de Miller-Rabin, método probabilístico estupendo para números gigantescos, pero para pequeños no es tan interesante. Básicamente se ha traducido esta versión http://en.literateprograms.org/Miller-R ... %28Java%29
Este último método es un test que dice si el número es primo o no, las demás funciones además devuelven en @extended el divisor mínimo cuando el número es compuesto. El test de Miller-Rabin es infalible para números compuestos. Cuando el número es primo hay una pequeña probabilidad de fallo. Esta probabilidad es acotable, por ejemplo yo ejecuto el test 20 veces, lo que da una probabilidad de acierto del 99,99999999990905% ,que es bastante alta