En este artículo se describirá el funcionamiento de la criba de Eratóstenes y su aplicación en varios lenguajes.
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
3- Enumerar los múltiplos de p desde 2p hasta el final de la lista y marcarlos en la lista
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
Al finalizar el algoritmo todos los números no marcados en la lista son números primos.
//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!
En este artículo veremos cómo crear DataFrames con Pandas manualmente, a partir de estructuras de Python, diferentes tipos de archivos, bases de datos y consultas a APIs. Los DataFrames en Pandas son estructuras de datos Leer más…
En este artículo veremos cómo utilizar Blueprints para modularizar nuestras aplicaciones Flask para hacerlas fácilmente escalables. También veremos como utilizarlos para gestionar los recursos de cada módulo. El micro-framework Flask tiene entre sus principales características Leer más…
En este artículo veremos como crear un DataFrame en Pandas a partir de un archivo CSV. Revisaremos algunas de las técnicas para el manejo de estos archivos y la selección de elementos del DataFrame como Leer más…
