Vikman's Blog

"Sieve for Seven", Scot Nelson . Los números primos son aquellos números naturales mayores que 1 que sólo tienen dos divisores: el 1 y él mismo. Hay muchos problemas en Matemáticas relacionados con los números primos, algunos de ellos aún sin resolver, como la Conjetura de Goldbach . El objetivo de hoy será hallar todos los números primos hasta 2·10 9 . Existen varios algoritmos para obtener listas de números primos, tal vez el más común sea la criba de Eratóstenes , que consiste en escribir una lista con todos los números que queremos estudiar y, partiendo del primero, tachar todos sus múltiplos, y repetir el proceso cada vez con el primer número que no hayamos tachado. Este algoritmo presenta dos problemas: Es destructivo (consiste en descartar), por lo que a priori consume demasiada memoria, y mucho tiempo en escribir candidatos. Eliminar objetos de una lista impide trabajar con ella desde otra hebra, ni siquiera para iterar, con lo que perdemos la posibilid...

Esta historia parte de un pequeño proyecto de antaño en el que intenté implementar la herramienta de relleno de Paint o Photoshop. Estamos hablando de un algoritmo de relleno por difusión : el objetivo es pasar por todos los puntos no coloreados partiendo de uno arbitrario y la solución se antojaba sencilla: un algoritmo de  backtracking .  Estuve cerca de lograrlo pero cuando la superficie a rellenar era medianamente grande, el programa se colgaba por desbordamiento de pila . El problema es que, al tratarse de una función recursiva , con cada paso que daba había que guardar en la pila el punto anterior, y si el espacio es grande podemos estar hablando de miles o millones de pasos. Esta información se guarda en la pila de llamadas , una zona de memoria especialmente rápida... y pequeña. La solución es muy fácil: convertir la función recursiva en iterativa , y guardar cada punto a explorar dentro de un contenedor de pila ( QStack en la biblioteca Qt), cu...