Python中的Eratosthenes筛非常慢

Question

我用Python编写了一个程序,它找到了给定数字(n)以下的所有素数,并总结它们(回答Project Euler的问题10).为了解决这个问题,我需要将2,000,000以下的所有素数加起来.我的程序有效,但似乎非常低效(当n = 2,000,000时,即使在30分钟后它也不会显示答案).我找到了另一个快得多的程序,虽然我似乎无法找出是什么让我的速度慢于我发现的速度.这是两个程序:

慢节目(我写的那个):

def print_sum(n):

    prime_array = {}
    sum = 0

    for i in range(2, n+1):
        prime_array[i] = 1

    prime_array[0] = 0
    prime_array[1] = 0

    for j in range(2, int(math.sqrt(n)) + 1):
        if prime_array[j] == 1:
            for k in range(2, n + 1):
                prime_array[j*k] = 0

    for x in prime_array:
        if prime_array[x] == 1:
            sum = sum + x

    print sum

print_sum(2000000)

快速计划:

n = 2000000
prime_array = [True] * n
sum = 0

def mark(prime_array, x):
    for i in xrange(x+x, len(prime_array), x):
        prime_array[i] = False


for x in xrange(2, int(len(prime_array)** .5) + 1):
    if prime_array[x]: mark(prime_array, x)

for y in xrange(2, n):
    if prime_array[y]:
        sum = sum + y

print sum

提前致谢!

Answer 1

        for k in range(2, n + 1):
            prime_array[j*k] = 0

看起来你已经通过这个循环超越了有用的范围.假设j是999并且n是1,000,000.然后prime_array将不得不钥匙高达9.99亿,即使你只关心键从0到100万.

尝试将您的分配限制为低于n的值.

        for k in range(2*j, n + 1, j):
            prime_array[k] = 0