Criba de Eratóstenes

¿Qué es la criba de Eratóstenes? Esta página explica qué es, quién la inventó, y utiliza el lenguaje de programación Logo para construir la criba utilizando los pixeles de la pantalla como la cuadrícula de la tabla.

Contenido

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.

Imagen: criba eratostenes 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

Imagen: criba eratostenes

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

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.

8. Preguntas, Dudas, Comentarios, Peticiones

Síguenos en Facebook

9. Enlaces

Lenguaje de Programación Logo

Cálculo de Factores Primos y Divisores


Generado con PureJoy. Creación: 11:15 - Dec 15, 2017. Última Modificación: 17:11 - Apr 02, 2023