Python中的Eratosthenes小型篩網

我需要在Python中實現Sieve of Eratosthenes，但由於它在大量代碼中的部分，因此希望儘可能緊湊地實現它。雖然有很多更有效的方法來完成查找素數，但我想看看Python能夠以瘋狂的緊湊性爲我做些什麼。Python中的Eratosthenes小型篩網

程序需要詢問用戶輸入，然後使用從2到輸入數字（包含）的篩選輸出所有素數。

我能得到到目前爲止最好的是：

n = int(input("To what n do you wish to find primes? ")) 
sieve = list(range(2, n+1)) 
for i in range(len(sieve)): 
    for j in range(i+1, len(sieve)): 
     if sieve[i] == 0: 
      continue 
     if sieve[j] % sieve[i] == 0: 
      sieve[j] = 0 
print([i for i in sieve if i != 0])

除此之外，我有麻煩了進一步冷凝的代碼。

編輯：在問這個問題之前，找不到讓這個問題重複的答案，因爲我被掛在專門搜索「Eratosthenes緊湊篩」及其變體之前。謝謝！

來源

2014-10-06 UnlimitedInf

這可能是在任http://codereview.stackexchange.com/或http://codegolf.stackexchange.com/更合適，這取決於是否你的主要目標是「儘可能小巧，不可讀」或「儘可能小巧，即使它變得不可讀」。 – Brian 2014-10-06 14:35:17

http://bytes.com/topic/python/answers/455979-shortest-prime-number-program – 2014-10-06 14:40:53

這就是我想出了：

n = [False for i in range(int(input('> '))+1)] 
n[0] = n[1] = True 
for i in range(2, len(n)): 
    for j in range(i+1, len(n)): 
     n[j] = ((j % i) == 0) if not n[j] else n[j] 
print([i for i in range(len(n)) if not n[i]])

來源

2014-10-06 14:44:39 rotestein

Python中的Eratosthenes小型篩網

回答

相關問題