[c&p] El número (2^1127239+2^563620+1)/5 de 339333 dígitos propuesto por Borys Jaworski (2006-Nov) encabeza el top. En esa lista aparecen un montón de números de los que no sabe con certeza si son primos o no, porque no son fáciles de descomponer ni se puede demostrar que sean primos. Entre las pruebas que se realizan a estos números se les comprueban los factores primos triviales, todos los divisores posibles hasta 2^32 y se les hacen otras perrerías variadas para ver si se pueden descomponer. [Seguir leyendo comentario #1]
Esas "perrerías" es lo que llamamos un "algoritmo voraz". No nos da los resultados con un 100% de certeza, pero es muchísimo más eficiente.
Lo contrario, un "algoritmo exhaustivo", es el que examina todas las posibilidades y nos da un resultado cierto al 100%. Obviamente toma mucho más tiempo, tal vez más tiempo del que disponemos.
Comentarios
continuando ... Si pasan esas pruebas, se les llama «primos probables», pero no son definitivamente primos.
vía Microsiervos: http://www.microsiervos.com/archivo/ciencia/nuevo-primo-probable.html
Esas "perrerías" es lo que llamamos un "algoritmo voraz". No nos da los resultados con un 100% de certeza, pero es muchísimo más eficiente.
Lo contrario, un "algoritmo exhaustivo", es el que examina todas las posibilidades y nos da un resultado cierto al 100%. Obviamente toma mucho más tiempo, tal vez más tiempo del que disponemos.