Criba de Eratóstenes – Algoritmos antiguos

Publicado por Andrea Navarro en

EratóstenesLa 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.

Criba de Eratóstenes – Algoritmo

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

 

 

 

 

 

 

 

 

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

Criba de Eratóstenes

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;
}

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