gatest escribió:Muchas gracias por toda esa info
@Ingalius Solo por curiosidad, no podríamos utilizar la criba de Eratóstenes para hallar primos exageradamente grandes como el que has puesto tu de ejemplo? O sería el mismo problema, a groso modo lo que has dicho: miles de PC conectados y calculando durante miles de años? Creo que no se ni para que pregunto si creo que se la respuesta jejeje
Nuevamente gracias por la info. Salu2
La criba de eratostenes, creo que es el primer "test de primalidad" conocido.
El algoritmo es eficiente para calculoar todos los numeros primos hasta el numero n. Con la particularidad, como bien apuntas, de que nos da TODOS los numeros primos comprendidos entre 1 y n.
Pero es un algoritmo tremendamente ineficiente, porque es un algoritmo exponencial tanto en tiempo como en espacio.
De echo, es facil comprobarlo con un simple programa informatico, o mas facil aun con papel y lapiz.
por ejemplo, calcular todos los primos menores que 80.
Raiz de 80 < 9.
Los primos menores de 9 son 2,3,5 y 7.
Construimos la lista de todos los numeros, desde el 1 hasta el 9.
Marcamos en la lista el 1, y todos los numeros multiplos de 2,3,5 y 7... es decir, el 4,6,8,10,12,14,15,16,18......
Los numeros que quedan sin marcar, son primos. Y asi tenemos todos los primos menores que 80.
Ahora, haz lo mismo con 160.
Y luego con 320.
Solo has de mirar, tanto el espacio que te ocupa, como el tiempo que tardas en aplicar el algoritmo.
Y, como muy bien supones, volvemos al mismo problema. Calculos fuera de nuestro alcance de calculo actual.
Si os interesa el tema, actualmente para calcular numeros primos enormes se utilizan otros "test de primalidad".
Los test de primalidad los hay de dos tipos, deterministicos y probabilisticos.
Los deterministicos nos aseguran si el numero primo que buscamos, es en realidad primo o no al 100%, pero siguen sin ser eficientes en tiempo y espacio de calculo. Requieren muchisimo calculo.
Los probabilisticos, hay varios "tests" diferentes, no nos aseguran al 100% si el numero es primo o no, pero tienen una probabilidad de error bajisima. Y tienen la ventaja de que el tiempo (y espacio) de calculo son mucho mas eficientes.
Estos ultimos son los que se utilizan en relacion a la criptografia.
Podeis buscar en el google por "test de primalidad" y encontrareis muchisima informacion en español.
Un saludo!!
, otro que pasa a agradecer el comentario de @Ingalius 
![[tadoramo]](/images/smilies/adora.gif "Adorando")
