Código en python para hacer "La criba de Eratóstenes"

Bueno como ya es de saberse en cada uno de los post donde exponga algún código de python sera de la versión 3.1 ó >, entonces no cabe la necesidad de estar mencionando la versión del lenguaje en el título del post.

Les presento un par de algoritmos muy parecidos ya que los dos usan la llamada criba de Eratóstenes para "cribar" los números primos de una sequencia de números. Ambos usan una sequencia 1..2000000.

La criba de Eratóstenes

 

 

Nota:

Si conoces algún algoritmo más eficiente tienes la libertad de comentarlo, gracias

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#inicializamos el tamano de la sequencia de numeros
n = 2000000
#se usa un conjunto porque es mas eficiente
#(no hay numeros repetidos)
noprimos = set()
 
#iteramos desde 2 hasta la raiz cuadrada de n
#y desde lo que lleva i, hasta n / i
#esto nos permite obtener todos los multiplos de i
#y agregarlos a el conjunto noprimos
for i in range(2, int(n ** .5) + 1):
    if i not in noprimos:
        for j in range(i, int(n / i) + 1): noprimos.add(i * j)
        
#por ultimo creamos una lista con todos los numeros
#primos desde 2 hasta n
primos = [p for p in range(2, n + 1) if p not in noprimos]

Créditos:

http://es.wikipedia.org/wiki/Criba_de_Eratóstenes

 

y aquí esta el otro que a mi parecer es más eficiente

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#inicializamos la criba como una lista con n elementos True
 
criba = [True] * n
 
#iteramos desde 2 hasta la raiz cuadrada de n
#y desde lo que lleva i, por i, hasta n
for i in range(2, int(n ** .5) + 1):
    for j in range(i * i, n + 1, i):
        #esto nos permite poner False en la posicion j - i de la criba
        #porque j es un multiplo de i y por lo tanto no es primo
        criba[j - 1] = False
 
#por ultimo "cribamos" todos los numeros primos desde 2
#hasta la longitud de la criba
primos = [p for p in range(2, len(criba) + 1) if criba[p - 1])]


Créditos:

http://www.s-anand.net/euler.html




Leave comments

authimage
  • Yo he creado una modificacion de la criba que es varios millones de veces mas rapida que esta, hace parecer a cualguier lenguaje en un lenguaje C, pero tengo un problema, como calculo los numeros extremadamente grandes y esto y el espacio en disco, si guardo en una base de datos los discos de Yeras se vuelven pequeños. Un numero de un n millon de digitos es un mega. Mil de ellos un gigabye. Un millon un terabyte, es decir si se almacenara como ascii, se pdria almacenar mas o como bit, pero dificultaria mucho los calculos y hacerlo mas lento.

    • ivan
  • Y no te animas a publicar la version modificada? Saludos Jorge Luna

    • pythonista

Copyright(c) 2017 - PythonBlogs.com
By using this website, you signify your acceptance of Terms and Conditions and Privacy Policy
All rights reserved