质数代码的优化

Question

这是我用Python写的代码，用来计算小于某个给定数字的所有质数的和。
我还能做些什么来优化它呢？

import math
primes = [2,]                      #primes store the prime numbers



for i in xrange(3,20000,2):                    #i is the test number
    x = math.sqrt(i)
    isprime = True
    for j in primes:               #j is the devider. only primes are used as deviders
        if j <= x:
            if i%j == 0:
                    isprime = False
                    break


    if isprime:
        primes.append(i,)


print sum (primes,)

Answer 1

primes = primes + (i,) 这个写法效率很低。每次循环的时候，它都会复制所有的元素，这样就把原本优雅的动态编程方案变成了一个 O(N²) 的算法。建议使用列表来代替：

primes = [2]
...
    primes.append(i)

另外，在循环中，当你检查到 sqrt(i) 的时候就可以提前退出循环。而且，因为你在处理素数列表的时候，肯定会在到达列表末尾之前就检查到 sqrt(i)，所以可以直接在原来的列表上更新，而不是先存一个 isprime 之后再用：

...
if j > math.sqrt(i):
    primes.append(i)
    break
if i%j == 0:
    break
...

最后，虽然这和性能没有关系，但用 range 比用 while 更符合 Python 的风格：

for i in range(3, 10000, 2):
    ...

Answer 2

还有一个可以优化的地方是，把 sqrt 的计算放到内层循环外面。毕竟，i 在这个循环中是保持不变的，所以每次都重新计算 sqrt(i) 是没有必要的。

Answer 3

你可以使用一种叫做埃拉托斯特尼筛法的算法，这种方法会更快，但需要更多的内存。你需要保持一个标记数组，用来表示每个数字是否是质数。每当找到一个新的质数时，就把这个质数的所有倍数在数组中标记为零。

N = 10000

# initialize an array of flags
is_prime = [1 for num in xrange(N)]
is_prime[0] = 0 # this is because indexing starts at zero
is_prime[1] = 0 # one is not a prime, but don't mark all of its multiples!

def set_prime(num):
    "num is a prime; set all of its multiples in is_prime to zero"
    for x in xrange(num*2, N, num):
        is_prime[x] = 0

# iterate over all integers up to N and update the is_prime array accordingly
for num in xrange(N):
    if is_prime[num] == 1:
        set_prime(num)

primes = [num for num in xrange(N) if is_prime[num]]

如果你使用高效的位数组，比如在这个例子中（向下滚动页面，你会找到埃拉托斯特尼筛法的例子），其实你可以处理相当大的N。