Python-Eratosthenes-小型蟒蛇篩

Question

這是我使用Eratosthenes篩尋找素數的代碼。

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) 

試圖找到一種方法來壓縮這些嵌套的for循環變成某種發生器或理解的，但它似乎沒有，你可以使用一個理解函數應用到列表中。我嘗試使用地圖和過濾器，但我似乎無法做到正確。

思考這樣的事情：

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]) 

顯然不適合十幾原因工作。如果我只是使用該代碼的過濾器部分：

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

什麼是把兩個變量到拉姆達的正確方法？ （a，i）使它成爲一個元組，但我想將'a'和'i'作爲獨立變量提交給lambda。

我最終解決這一個班輪問題：

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)) 

Answer 1

這不正是你的循環的直接翻譯，但它是非常接近，緊湊：

>>> 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] 

雖然我d建議a > i而不是a != 0更短更快;）

Answer 2

首先要注意的是，你寫的不是篩埃拉托色尼。看看有多少迴路埃拉托色尼的太傻太天真篩執行：

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 

測試：

>>> 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環路100號（不包括排序）。對於100個號碼（不包括在端部過濾器）

>>> 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循環：這可以通過一些小的改動加以改進：

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 

測試。現在看看你的：

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 

測試：

>>> 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) 

更糟糕：

>>> [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] 

在n = 10000，您的實現做幾乎100倍之多的工作！

我的建議是在做出「緊湊」之前創建一個合理的實現。代碼高爾夫可以很有趣，但是無論長度如何，它都不具有挑戰性，或者不像編寫高效的代碼那樣具有挑戰性。

也就是說，考慮這個單線程（如果您不計算導入，可以使用lambda x, y: x - y代替operator.sub）。這實現了第一個小改進的算法：

>>> 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]) 

Answer 3

你不是在做Eratosthenes的篩子;沒有正確實施算法的危險在於它會非常緩慢。例如，在10**6上試試你的算法。

最短執行埃拉托色尼的包圍篩的我能想出：

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] 

演示：

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

它實際上是相當簡潔的，如果忽略換行符和大量的跳躍，偶數數字優化：

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

Answer 4

以下單線程不是重新在所有遲來到您的代碼：

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

就像你的代碼，這仍然是沒有真正埃拉托色尼的篩，因爲，例如，它會徒勞地試圖劃掉倍數6和9等。儘管如此，對於小於100萬或更多的值，仍然比大多數其他Sieve外觀快得多，因爲對於小N，「非常」的素數與非素數（數量爲< N的素數部分是1/log(N)）幾乎相同。

重從源代碼修改，可能比原來低效率：http://codeblog.dhananjaynene.com/2011/06/10-python-one-liners-to-impress-your-friends/

Answer 5

這裏的篩的一個簡單的演示。請注意，lambda不用作過濾函數，因爲素數需要在定義時綁定。另外值得關注的是，從不重複分歧的意義上說它是有效的，但從長遠來看，它可能導致you-know-what。

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] 

Answer 6

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:] 

Answer 7

這裏是最緊湊的真實篩我想出了這麼遠。這表現令人驚訝。

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]    

這個稍微複雜一點的版本是我所見過的速度最快的：

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))    

這裏是一個真正的篩子的列表理解：

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]