0

我正在尝试计算所有低于 200 万的素数的总和，因为我已经编写了一个函数来查找小于给定数字的素数，所以我只是编写了一个新函数，它调用旧函数并将该列表中的项目。

但它似乎需要永远。如何加快此代码的速度？

def find_primes(n):
    "Find the prime numbers below n"
    primes=[];
    for i in range(2,n):
        for fac in range (2,i):
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

def add_primes(m):
    "Sum all the prime numbers below m"
    newlist=find_primes(m);
    t=sum(newlist);
    return t

PS：我是一个Python新手，所以如果你能很好地解释我的错误，我会很高兴。提前致谢。

4

2 回答 2

3

实施埃拉托色尼筛法。这将使您的代码比目前做的工作少得多，使其速度更快。

于 2013-03-24T13:59:08.540 回答
0

fac in range (2,i)您可以通过将 for行替换为以下代码来改进当前代码：

for fac in primes:

代码：

def find_primes1(n):
    "Find the prime numbers below n"
    primes=[2,3]     #initialize primes with 2 values
    for i in range(4,n):
        for fac in primes:
            if i!=fac and i%fac == 0:
                break
        else:
            primes.append(i)
    return primes

时间比较：

In [6]: %timeit find_primes(10**4)   # your version
1 loops, best of 3: 2.33 s per loop

In [7]: %timeit find_primes1(10**4)
1 loops, best of 3: 171 ms per loop

In [8]: find_primes1(10**3)==find_primes(10**3)
Out[8]: True

但是对于较大的值，您绝对应该学习Eratosthenes 筛法。

于 2013-03-24T14:08:45.597 回答