Criba de Eratóstenes

Criba de Eratóstenes

La criba de Gustavo Rivas Gervilla y juan carlos ordoñez ramos con la colaboracion de adrian miron y kiko reyes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.

Pseudocódigo

Algoritmo Criba de Eratóstenes (Complejidad ${\mathcal {O}}(n~\log ^{2}n~\log \log n)$)

Entrada: Un número natural $n$ Salidasol: El conjunto de números primos anteriores a $n$ (incluyendo $n$) Escriba todos los números naturales desde $2$ hasta $n$ Para $i$ desde $2$ hasta $\lfloor {\sqrt {n}}\rfloor$ haga lo siguiente: Si $i$ no ha sido marcado entonces:de dos en dos asi sucesivamente Para $j$ desde $i$ hasta $n\div i$ haga lo siguiente: Ponga una marca en $i\times j$ El resultado es: Todos los números sin marca

Acerca de la notación:

• $\lfloor x\rfloor$ es la función parte entera de $x$
• $a\div b$ es el cociente de dividir $a$ entre $b$

Para su implementación en una computadora, normalmente se maneja un vector de tipo lógico con $n$ elementos. De esta manera, la posición $i$ contiene el valor Verdadero como representación de que $i$ ha sido marcado y Falso en otro caso.

Véase también

• Test de primalidad

Referencias

• Samuel Horsley (1772). «${\text{KO}}\Sigma {\text{KINON EPATO}}\Sigma \Theta {\text{ENO}}\Upsilon \Sigma$. or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S.». Philosophical Transactions (1683-1775) 62. 
• Walter Mora F. «Criba de Eratóstenes». Revista digital Matemática: Educación e Internet 7 (2).