Criba de Eratóstenes – Algoritmos antiguos

Publicado por Andrea Navarro en

En este artículo se describirá el funcionamiento de la criba de Eratóstenes y su aplicación en varios lenguajes.

Eratóstenes

La Criba de Eratóstenes es un algoritmo que permite encontrar los números primos dentro de una serie de números naturales. Fue diseñado por Eratótenes, un matemático, geógrafo, poeta, astrónomo y músico griego que vivió en el siglo II AC y llegó a convertirse en el encargado de la biblioteca de Alejandría.

Aunque hoy en día no tiene mucha utilidad como herramienta para encontrar nuevos números primos si es utilizado para comparar la velocidad entre diferentes lenguajes.

Algoritmo de Criba de Eratóstenes

1- Obtener una lista de números enteros consecutivos comenzando por dos hasta la cantidad de números que quieran evaluarse

2- Inicialmente hacer p=2 el número primo más pequeño

Criba de Eratóstenes

3- Enumerar los múltiplos de p desde 2p hasta el final de la lista  y marcarlos en la lista

Criba de Eratóstenes

4- Encontrar el siguiente numero mas pequeño que sea mayor que p y que no esté marcado. Si no existe tal número el algoritmo termina. Si existe entones p=nuevo numero y un número primo.

5-Repetir desde el paso 3

Criba de Eratóstenes

Criba de Eratóstenes
Criba de Eratóstenes
Criba de Eratóstenes
Criba de Eratóstenes

Al finalizar el algoritmo todos los números no marcados en la lista son números primos.

Pseudocódigo con Pseint

//Criba de Eratóstenes
Proceso CribaEratostenes
	//Obtener las lista de números a evaluar
	limite=16 
	Dimension numeros[limite]
	//Obtener las lista de números a evaluar
	Para i=2 Hasta limite Con Paso 1 Hacer 
		numeros[i]=Verdadero; 
	FinPara 
	//Hacer 2 el primer número primo 
	numeros[2]=Verdadero;
	//Recorrer los números y para cada uno 
	Para n=2 Hasta limite Con Paso 1 Hacer 
//Si es primo recorrer los múltiplos y marcarlos como no primo 
		Si numeros[n]==Verdadero 
			Para i=n*n Hasta limite Con Paso n Hacer
				numeros[i] = Falso;
			FinPara
		FinSi
	FinPara
	//Muestro la lista de los primos 
	Escribir "Primos" 
	Para n=2 Hasta limite Con Paso 1 Hacer
		Si numeros[n]==Verdadero
			Escribir n 
		FinSi 
	FinPara 
FinProceso

Algoritmo para PHP

<?php
//Criba de Eratóstenes
//Obtener las lista de números a evaluar
$limite=16;
for($i=2;$i<$limite;$i++)
{
  $numeros[$i]=true;
}

//Hacer 2 el primer número primo
$numeros[2]=true;

//Recorrer los números y para cada uno
for ($n=2;$n<$limite;$n++)
{
  //Si es primo recorrer los múltiplos y marcarlos como no primo
  if ($numeros[$n])
  {
    for ($i=$n*$n;$i<$limite;$i+=$n)
    {
       $numeros[$i] = false;
    }
  }
}

//Muestro la lista de los primos 
echo "Primos: ";
for ($n = 2; $n < $limite; $n++)
{
  if ($numeros[$n])
  {
    echo $n." ";
  }
}

Algoritmo para C

#include<stdio.h>
#define LIMITE 16 
//Criba de Eratóstenes
int main(int argc, char** argv){
	int i,j,n;
	int numeros[LIMITE];
    
	//Obtener las lista de números a evaluar
	for(i=2;i<LIMITE;i++){
		numeros[i]=1;
	}
	
	//Hacer 2 el primer número primo
	numeros[2]=1;
 
	//Recorrer los números y para cada uno
	for (n=2;n<LIMITE;n++){
//Si es primo recorrer los múltiplos y marcarlos como no primo
		if (numeros[n]){
			for (i=n*n;i<LIMITE;i+=n){
				numeros[i] = 0;
			}
		}
	}
	  
	//Muestro la lista de los primos	
	printf("Primos: ");
	for (n = 2; n < LIMITE; n++){
		if (numeros[n]){
			printf("%d  ",n);
		}
	}
    
	return 0;
}

Algortimo para Python

#Criba de Eratóstenes
#Obtener las lista de números a evaluar
limite = 16
primos = []
numeros= []
for i in range(1,limite+1):
	numeros.append(True)
#Recorrer los números y para cada uno
for n in range(2, limite):
	#Si es primo recorrer los múltiplos y marcarlos como no primo
	if numeros[n]:
		for i in range(n*n,limite,n):
			numeros[i] = False
#Mostrar la lista de los primos
print("Primos: ")
for n in range(2, limite):
	if numeros[n]:
		print(str(n)+" ")

Este código es solamente una de las aplicaciones posibles de este algoritmo, también puede resolverse sin utilizar arreglos o teniendo una lista separada donde agregar los números primos encontrados.

Espero que les sirva para practicar en otros lenguajes de programación!


Andrea Navarro

- Ingeniera en Informática - Docente universitaria - Investigadora