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小型筛网

回答

相关问题