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:

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

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


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.

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

5. 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.

6. Preguntas, Dudas, Comentarios, Peticiones

Nombre:
Ciudad y País:
Email:
 

7. 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: 18:13 - Nov 05, 2018