Dice la Wikipedia que la criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado n. Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera: Comenzando por el 2, se tachan todos sus múltiplos; comenzando de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos, así sucesivamente. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que n.
Este fue probablemente uno de los primeros procedimientos para hallar estos fascinantes números primos, que son en gran medida el sostén de la teoría de números. Obviamente el buscar primos así bien puede hacerse por computadora y ya a alguien se le ocurrió implementar la tabla de Erastóstenes usando un chip ARM.
Si se trata de hacer lo mismo que se hace en el agoritmo de la tabla de Erastóstenes, es necesario pensar no en el procedimiento en sí, sino en cómo guardar una tabla grande de números en la memoria de un microcontrolador teniendo siempre poco espacio. La idea del autor, Mike Szczy, fue hacwer una tabla de booleanos (que llamó un “packed array de bits”). Los detalles de todo su trabajo pueden verlo en las referencias.
¿Por qué alguien se preocuparía por hacer este tipo de experimentos con un controlador ARM? De acuerdo al autor, le interesaba ver la funcionalidad del manejo de bits en el núcleo del ARM. Estos chips tienen direcciones “alias” que mapena un solo bit en la SRAM y asdemás, tienen algunos registros periféricos. Esto permite leer o escribir bits usando una sola instrucción. Un efecto colateral de esto es que se tienen direcciones para toda esta arquitectura en 32 bits.
referencias: