Test números primos

[Ximorro]

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.

PrimosPant.png (1.06 KiB) Visto 4314 veces

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

[tander]

No entiendo como utilizarlo. Lo ejecuto y nada...
Me interesa mucho la aplicación :D

[Ximorro]

Es que el resultado lo saca por la consola, tendrás que ejecutarlo desde Scite o desde consola y editarlo (comentar y descomentar cosas) para hacer los distintos tests.

Ahora mismo lo que hace es ejecutar

Código: Seleccionar todo

Local $tIni = TimerInit()
ConsoleWrite(_EsPrimo7(10000000000037) & ", Divisor: " & @extended)
ConsoleWrite(@CRLF & TimerDiff($tIni) & " ms" & @CRLF)

Es decir, imprime en consola si el número 10000000000037 es primo, y efectivamente, pues el resultado es:
True, Divisor: 0
1292.12262836881 ms

Por ejemplo para conseguir una salida como la que puse en el post, se ejecuta el segundo test, que básicamente hace esto:

Código: Seleccionar todo

Local $tIni = TimerInit()
For $i = 1000000000001 To 1000000000250 Step 2
	ConsoleWrite($n & "->")
	If _EsPrimo7($n) Then
		ConsoleWrite("PRIMO" & @CRLF)
	Else
		ConsoleWrite("Divisor: " & @extended & @CRLF)
	EndIf
Next
ConsoleWrite(TimerDiff($tIni) & " ms" & @CRLF)

La utilidad de este programita no es para el usuario final, sino para el programador al que le interesen este tipo de rutinas. En realidad es un estudio para ver cómo hacer esto de comprobar la primalidad de enteros en AutoIT. Si lo necesitas te recomiendo tomar la función _EsPrimo7(). Aunque es un poco fea de aspecto es notablemente la más rápida, además, igual que las otras versiones _EsPrimoXX() ofrece en @extended el divisor menor cuando el número es compuesto.

El test de Miller-Rabin no ofrece divisores porque no los busca, funciona de otra manera. Este test es una pasada para números muy grandes, desgraciadamente en AutoIt no tiene gran utilidad debido a la limitación con los enteros sólo se puede usar para números hasta 2^26 aprox. Y encima no es tan rápido, para esos números "pequeños" se acaba antes buscando divisores; sería útil para números grandes pero están fuera de rango. En Java hice una versión que usaba BigInteger (un invento para tener enteros del tamaño que quieras) y ahí sí era interesante.

Me temo que la conclusión a la que llegué es que AutoIt aunque es maravilloso para interactuar con Windows y muchas cosas más, no es muy bueno para computación masiva.
Como comento en otro post hablando de lenguajes interpretados, resulta que esta rutina AutoIt me tarda 46.6 segs en ver que 9007199254740881 es primo. En Java (y por supuesto en el mismo ordenador) exactamente el mismo método me lo ejecuta en 0.57 segs... ¡¡casi 100 veces más rápido!!

Así que si quieres hacer cosas serias en computación igual conviene que mires otros lenguajes. Si lo necesitas en AutoIt aquí tienes mis funciones si te interesan. Como digo recomiendo _EsPrimo7(). Si las usas no te olvides de los créditos

Por supuesto si tienes dudas adelante, aunque respecto a seguir investigando el tema por mi parte lo dejé cerrado, dadas las conclusiones de rendimiento a las que llegué...