1

所以我今晚花了很多时间来组装这个基于 Eratosthenes 筛的 Prime 生成器。这是代码:

n = input("What number do you want to calculate to? ")
import time
start = time.time()
def pr(l):
  ln = l+1
  p = range(2, ln)
  for k in p:
    f = range(k, ln, k)
    for f in f[1:]:
       if f in p:
          p.remove(f)
    return p
print pr(n)
end = time.time() - start
print "This took: ",end  

我认为我想做的主要事情是加快速度。我很确定将p.remove(f)功能更改为类似的功能p[f] = 0会加快速度,但这不起作用。有谁知道我做错了什么?还是有更快的方法来做到这一点?

4

1 回答 1

0

这是我的埃拉托色尼筛法:

def primes(n): # sieve of eratosthenes
    ps, sieve = [], [True] * (n + 1)
    for p in range(2, n + 1):
        if sieve[p]:
           ps.append(p)
           for i in range(p * p, n + 1, p):
               sieve[i] = False
    return ps

请计时,让我知道它与您的版本相比如何。

于 2013-09-26T10:58:13.173 回答