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. ¿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. 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. Tabla de Números Primos para Imprimir

Imagen: tabla de criba de eratostenes


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 [Documento en PDF].

6. Licencia

Este es un documento libre.

Autor: Daniel Ajoy

Creative Commons License
Esta obra está licenciada bajo una Licencia Creative Commons Atribución-Compartir Obras Derivadas Igual 2.5 España.

7. Preguntas, Dudas, Comentarios, Peticiones

Nombre:
Ciudad y País:
Email:
 

8. Enlaces

Página Principal

Creación de Tabla de Factores Primos y Divisores para Imprimir


Generado con PureJoy.
Fecha: 15:58 - Jul 23, 2013