Criba de Eratóstenes

Cálculo de números primos menores a 40000 utilizando el algoritmo de la Criba de Eratóstenes. Los puntos de la pantalla serán el medio de almacenamiento de los cálculos parciales. Usamos el lenguaje de programación Logo (Intérprete FMSLogo)

Contenido

1. Introducción
2. Visualización del Proceso
3. Explicación General
4. Detalles
5. Tabla de Números Primos para Imprimir
6. Licencia
7. Preguntas, Dudas, Comentarios, Peticiones
8. Enlaces

1. Introducción

La Criba de Eratóstenes es un procedimiento para determinar todos los números primos hasta cierto número natural dado. Esto se hace recorriendo una tabla de números usando el siguiente algoritmo:

Empezamos en el número 2, resaltamos el número 2 como primo pero tachamos todos los múltiplos de 2 (es decir, tachamos 4, 6, 8, etc.).
Se continua con el siguiente número no tachado en la tabla, en este caso el número 3, resaltamos el número 3 como primo y tachamos todos los múltiplos de 3 (es decir tachamos 6, 9, 12, etc.).
El siguiente número no tachado en la tabla es el 5, resaltamos el número 5 como primo y tachamos todos los múltiplos de 5 (es decir tachamos 10, 15, 20, etc.).

Imagen: cr iba era to st en es 200

Ese es el resultado del proceso en una pequeña tabla de números hasta el 200. Es una tabla de 10x20. Las pantallas de los monitores de computadoras tienen más de 1000x1000 celdas. Lo siguiente describe cómo usar una pequeña área del monitor como una tabla para aplicar el método de la criba de Eratóstenes y encontrar todos los números primos hasta el 40000.

[ arriba ]

2. Visualización del Proceso

para inicio
haz "xmax 200
haz "xdis 1
haz "ydis 1
haz "xini -100
haz "yini 100        

haz "amarillo [255 255 0]
haz "gris [141 141 141]

borraPantalla 
ocultaTortuga

ponColorLapiz :amarillo criba0

ponColorLapiz :gris apaga 1 :xmax
números.primos 1 :xmax * :xmax
fin

Imagen: cr iba era to st en es

[ arriba ]

3. Explicación General

El procedimiento principal se llama inicio. Empezamos inicializando unas variables. Utilizaremos una criba cuadrada de xmax celdas por lado. Ya que xmax = 200 el número de celdas de nuestra criba será 200 x 200 = 40000. Cada celda será un pixel y la distancia entre celdas tanto horizontalmente como verticalmente será 1 (xdis e ydis es igual a 1). La esquina superior izquierda del cuadrado estará en una coordenada x inicial de xini = -100 y una coordenada y inicial de yini = 100.

El procedimiento criba0 inicializa la criba, colocando en las celdas píxeles de color amarillo. Los píxeles amarillos representan los números primos. Al inicio todos los números son considerados potenciales primos.

El procedimiento apaga va apagando las celdas, colocando en ellas píxeles grises. Los píxeles grises representan números descartados, no primos.

El procedimiento números.primos lee la criba, identifica los píxeles amarillos restantes y escribe los números primos calculados.

[ arriba ]

4. Detalles

El detalle de los procedimientos utilizados se presenta a continuación.

para criba0
repite :xmax * :xmax [
 subeLapiz ubica cuentaRepite - 1
 bajaLapiz avanza 1
]
subeLapiz
fin

para apaga :n :max
si :n = :max [alto]
subeLapiz 
haz "b buscapri :n :max
si :b = "nomas [alto]

ponRumbo 90 subeLapiz 
ponPos [115 65] cortaArea 50 50
ponPos [115 90] rotulo :b + 1

salta :b 1 :b + 1 :max * :max

apaga :b + 1 :max
fin

para números.primos :n :max
si :n = :max [alto]
ubica :n
si pixel = :amarillo [muestra :n + 1]
números.primos :n + 1 :max
fin

para salta :ini :n :salto :max
haz "m :ini + :n * :salto
si :m > :max - 1 [alto]
subeLapiz ubica :m 
bajaLapiz avanza 1
salta :ini :n + 1 :salto :max
fin

para buscapri :n :max
si :n = :max [devuelve "nomas]
ubica :n
si pixel = :amarillo [devuelve :n]
devuelve buscapri :n + 1 :max
fin

para ubica :n
ponX :xini + :xdis * (resto :n :xmax)
ponY :yini - :ydis * (entero :n / :xmax)
fin

[ arriba ]

5. Tabla de Números Primos para Imprimir

Imagen: ta bla de cr iba de era to st en es

Está es una Criba de Eratóstenes hasta el número 6499, para imprimir. La segunda fila corresponde a los números empezando el 100, así 101 es primo, 103 es primo, 107 es primo. La tercera fila corresponde a los números empezando en 200, así 211 es primo, 223 es primo, etc. Está contenida en una hoja formato A4, en PDF .