gpt4 book ai didi

python - Python 中的 Eratosthenes 筛法非常慢

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:30:41 27 4
gpt4 key购买 nike

我用 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

提前致谢!

最佳答案

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

看起来您将超出此循环的有用范围。假设 j 是 999,n 是 1,000,000。然后 prime_array 将拥有高达 999,000,000 的键,即使您只关心从 0 到 1,000,000 的键。

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

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

关于python - Python 中的 Eratosthenes 筛法非常慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34594933/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com