素数代码的优化

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

您可以使用一种名为Sieve of Eratosthenes的不同算法,它会更快但需要更多内存.保留一组标志,表示每个数字是否为素数,并且对于每个新素数集,它对于该素数的所有倍数都为零.

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做这个,例如在这个例子中(在页面上向下滚动,你会找到一个Sieve of Eratosthenes的例子).