Python- Tamiz de Eratóstenes- Compacto Python

Este es mi código para encontrar números primos usando el Tamiz de Eratóstenes.

list = [i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)] for i in list: for a in list: if a!=i and a%i == 0: list.remove(a) 

Tratar de encontrar una manera de comprimir los nesteds para bucles en algún tipo de generador o comprensión, pero no parece que pueda aplicar una función a una lista usando una comprensión. Intenté usar el mapa y el filtro, pero parece que no puedo hacerlo bien.

Pensando en algo como esto:

 print map(list.remove(a), filter(lambda a, i: (a%i ==0 and a!=i), [(a, i) for i in list for a in list]) 

Obviamente no funciona por una docena de razones. Si solo estuviera usando la parte del filtro de ese código:

 filter(lambda a, i: (a%i ==0 and a!=i), **[(a, i) for i in list for a in list]** 

¿Cuál es la forma correcta de poner dos variables en la lambda? (a, i) lo convierte en una tupla, pero quiero enviar ‘a’ e ‘i’ como variables independientes para colocar en la lambda.

Terminé resolviendo el problema con esta frase:

 print sorted(set([i for i in range(2, int(raw_input("Compute primes up to what number? "))+1)]).difference(a for i in l for a in l if a!=i and a%i == 0)) 

No es precisamente una traducción directa de tus bucles, pero es bastante estrecha y compacta:

 >>> l = range(2, 101) >>> sorted(set(l).difference(a for i in l for a in l if a!=i and a%i == 0)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Aunque sugeriría a > i lugar de a != 0 como más corto y más rápido;)

Lo primero que debes tener en cuenta es que lo que has escrito no es el tamiz de eratóstenes. Mira cuántos bucles ejecuta un tamiz totalmente ingenuo de eratóstenes:

 def sieve1(n): loops = 0 numbers = set(range(2, n)) for i in range(2, int(n ** 0.5) + 1): for j in range(i * 2, n, i): numbers.discard(j) loops += 1 return sorted(numbers), loops 

Probado

 >>> sieve1(100) ([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 178) 

178 bucles para 100 números (sin incluir la clasificación). Esto se puede mejorar con algunos cambios menores:

 def sieve2(n): loops = 0 numbers = range(0, n) for prime in numbers: if prime < 2: continue elif prime > n ** 0.5: break for i in range(prime ** 2, n, prime): numbers[i] = 0 loops += 1 return [x for x in numbers if x > 1], loops 

Probado

 >>> sieve2(100) ([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 102) 

102 bucles para 100 números (sin incluir el filtro al final). Ahora mira el tuyo:

 def sieve3(n): loops = 0 numbers = range(2, n) for i in numbers: for j in numbers: if j != i and j % i == 0: numbers.remove(j) loops += 1 return numbers, loops 

Probado

 >>> sieve3(100) ([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], 663) 

Se pone peor:

 >>> [sieve1(x)[1] for x in [100, 1000, 10000]] [178, 2978, 41723] >>> [sieve2(x)[1] for x in [100, 1000, 10000]] [102, 1409, 16979] >>> [sieve3(x)[1] for x in [100, 1000, 10000]] [663, 28986, 1523699] 

¡En n = 10000 , su implementación hace casi 100 veces más trabajo!

Mi sugerencia sería crear una implementación sensible antes de hacerla “compacta”. El golf de código puede ser divertido, pero no es tan difícil ni tan edificante como escribir código eficiente , sea cual sea la longitud.

Dicho esto, considere esto de una sola línea (si no cuenta la importación, de lo que podría deshacerse utilizando lambda x, y: x - y en lugar de operator.sub ). Esto implementa el primer algoritmo con una pequeña mejora:

 >>> from operator import sub >>> reduce(sub, (set(range(x ** 2, 100, x)) for x in range(2, int(100 ** 0.5) + 1)), set(range(2, 100))) set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]) 

No estás haciendo el Tamiz de Eratóstenes; El peligro de no implementar correctamente el algoritmo es que será extremadamente lento. Pruebe su algoritmo en 10**6 por ejemplo.

La implementación más corta del Tamiz delimitado de Eratóstenes que puedo encontrar:

 def primes(upTo): isPrime = list(range(upTo)) for p in range(2,int(upTo**0.5)+1): #p: 2,3,4,...,sqrt(N) print(p, isPrime[p]) if isPrime[p]: for multiple in range(p**2,upTo,p): #mult: p^2, p^2+p, p^2+2p, ..., N isPrime[multiple] = False return [x for x in isPrime[2:] if x] 

Manifestación:

 >>> list(primes(29)) [2, 3, 5, 7, 11, 13, 17, 19, 23] 

En realidad, es bastante sucinto, si ignora los saltos de línea y la optimización masiva de los números pares:

 isPrime=[True]*upTo for p in range(2,upTo): if isPrime[p]: yield p for m in range(p,upTo,p): isPrime[m]=False 

La siguiente frase no está relacionada en absoluto con su código:

 def primes(n): return set(range(2,n))-{c for i in range(2,n) for c in range(2*i,n,i)} 

Al igual que su código, este aún no es realmente el Tamiz de Eratóstenes porque, por ejemplo, tratará de cruzar múltiplos de 6 y 9 etc. Sin embargo, aún funciona más rápido que la mayoría de los otros parecidos al Tamiz para valores menores a un millones o más, ya que para N pequeño hay “aproximadamente tantos” primos como no primos (la fracción de números 1/log(N) ).

Muy modificado desde la fuente, posiblemente menos eficiente que el original: http://codeblog.dhananjaynene.com/2011/06/10-python-one-liners-to-impress-your-friends/

Aquí hay una simple demostración de la criba. Tenga en cuenta que lambda no se utiliza como función de filtrado, porque el número primo debe vincularse en el momento de la definición. También es interesante el hecho de que es eficiente en el sentido de no duplicar divisiones, pero a la larga podría llevarlo a saber qué .

 import itertools def primes(): ints = itertools.count(2) while True: p = next(ints) yield p ints = itertools.ifilter(p.__rmod__, ints) print list(itertools.islice(primes(), 10)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 
 def sieve(n): sieve_list = range(n) zero_list = [0] * n for i in range(2, int(n**.5) + 1): if sieve_list[i]: sieve_list[2*i:n:i] = zero_list[2*i:n:i] return filter(None, sieve_list)[1:] 

Aquí está el tamiz verdadero más compacto que he encontrado hasta ahora. Esto se realiza sorprendentemente bien.

 def pgen(n): # Sieve of Eratosthenes generator np = set() # keeps track of composite (not prime) numbers for q in xrange(2, n+1): if q not in np: yield q np.update(range(q*q, n+1, q)) >>> list(pgen(100)) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Esta versión un poco más compleja es la más rápida que he visto:

 def pgen(n): # Sieve of Eratosthenes generator by Dan Salmonsen yield 2 np = set() for q in xrange(3, n+1, 2): if q not in np: yield q np.update(range(q*q, n+1, q+q)) 

Aquí está un verdadero colador como una lista de comprensión:

 def primes(n): sieve = set(sum([range(q*q, n+1, q+q) for q in odds], [])) return [2] + [p for p in odds if p not in sieve] >>> primes(100) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

No es exactamente la solución más compacta, pero el argumento de paso en la función de rango en Python3 ayuda aquí.

 prime_sieve = [True] * (int(input('Primes Upto ?'))+1) # The first prime number for i in range(2, len(prime_sieve)): if prime_sieve[i]: for j in range(i+i, len(prime_sieve), i): prime_sieve[j] = False print(i, end=',')