Criba de Eratóstenes
Contenido
2. Criba de Eratóstenes hasta el 200
3. Criba de Eratóstenes usando Pixels como Memoria
4. Visualización del Proceso
5. Explicación General
6. Detalles
7. Licencia
8. Preguntas, Dudas, Comentarios, Peticiones
9. Enlaces
1. ¿Para qué sirve la criba de Eratóstenes?
La Criba de Eratóstenes es un procedimiento para determinar todos los números primos hasta cierto número natural dado. También se llama Criba de Eratóstenes a la tabla resultante de este proceso. Obviamente fue inventada por este señor.
El proceso consiste en recorrer una tabla de números usando el siguiente algoritmo:
- Haremos el 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)
- 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.).
2. Criba de Eratóstenes hasta el 200
Ese es el resultado del proceso en una pequeña tabla de números hasta el 200. Es una tabla de 10x20. Acá está el detalle del Proceso de creación de una criba de Eratóstenes hasta el 200.
3. Criba de Eratóstenes usando Pixels como Memoria
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.
4. 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
5. 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.
6. 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
7. Licencia
Este es un documento libre.
Autor: Daniel Ajoy
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.
8. Preguntas, Dudas, Comentarios, Peticiones
9. Enlaces
Cálculo de Factores Primos y Divisores