欧拉计划第十题 (Python)

Question

为什么我的算法在寻找200万以下所有质数的和时如此缓慢？我是一个相当初学者的程序员，这是我为解决问题而想出来的算法：

import time

sum = 2
start = time.time()

for number in range(3, 2000000):
    prime = True
    for x in range(2, number):
        if number % x == 0:
            prime = False
    if prime:
        sum += number

print "Sum =", sum
end = time.time() - start
print "Runtime =", end

有人可以帮我吗？ 谢谢！

- user2538722

---

因为你要循环200万次，超过两倍以上。尝试先进行筛选，只循环素数（提示：首先从奇数开始）。 - TerryA

Answer 1

你的算法使用了试除法，速度非常缓慢。更好的算法是使用埃拉托色尼筛法：

def sumPrimes(n):
    sum, sieve = 0, [True] * n
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

print sumPrimes(2000000)

这应该在不到一秒的时间内运行。如果您对使用质数进行编程感兴趣，我自谦地建议您阅读我博客中的文章。

- user448810

---

这是什么意思？sum，sieve = 0，[True] * n。我是编程新手，你能给我解释一下吗？ - smid_the_best

该语句将变量_sum_初始化为0，并创建一个长度为_n_的数组_sieve_，其中所有值最初都设置为布尔值_True_。你看过链接的文章吗？ - user448810

@user448810，为什么第二个for循环允许从p*p开始？它不应该只是从p开始，然后您随后删除所有p的倍数吗？ - Funzies

@Funzies：所有小于 p * p 的数字都已经被比 p 小的质数排除了。 - user448810

Answer 2

有许多优化可以做（也应该这样做，因为您将需要在欧拉计划的许多问题中进行素数生成，因此具有快速实现会简化后续操作）。

看一下Atkin筛法（以及相关筛法）(http://en.wikipedia.org/wiki/Sieve_of_Atkin)，了解如何通过算法来加速素数生成。

然后看一下对于这个S.O.-post的精彩答案(Fastest way to list all primes below N)，它记录了许多素数生成算法/实现的时钟。

- kamjagin

Answer 3

没有人指出这一点，但在Python 2.x中使用range非常慢。在这种情况下，应该使用xrange，这样可以大大提高性能。
请参见此问题。 另外，您不必循环直到您要检查的数字，检查round(sqrt(n)) + 1就足够了。（如果大于其平方的数字除以它，那么必定存在一个小于该平方数的数字，您必须已经注意到了。）

- unddoch

Answer 4

首先，我认为您可以通过定义一个函数来拆分代码。然而，在这种情况下使用常规函数的缺点是每次普通函数返回一个值时，下一次对该函数的调用将再次执行函数内部的完整代码。由于您需要迭代200万次，因此最好的方法是：

• 有一个函数可以给出下一个质数并临时将控制权返回给调用方。这些函数称为生成器。
• 要定义生成器函数，只需使用yield命令而不是return。
• 当您使用生成器时，就像知道该函数将再次被调用，当它发生时，函数内部的执行会在yield指令之后继续，而不是再次遍历整个函数。
• 这种方法的优点是在长时间的迭代中，您可以避免消耗系统的所有内存。

我建议您查看Python中有关生成器的文章。这篇文章为此示例提供了更详细的解释。

解决方案应该是这样的：

import math

# Check if a number is prime
def is_prime(number):
    if number > 1:
        if number == 2:
            return True
        if number % 2 == 0:
            return False
        for current in range(3, int(math.sqrt(number) + 1), 2):
            if number % current == 0: 
                return False
        return True
    return False

# Get the next after a given number
def get_primes(number):
    while True:
        if is_prime(number):
            yield number
        # Next call to the function will continue here!   
        number += 1 

# Get the sum of all prime numbers under a number
def sum_primes_under(limit):
    total = 2
    for next_prime in get_primes(3):
        if next_prime < limit:
            total += next_prime
        else:
            print(total)
            return

# Call the function
sum_primes_under(2000000)

- jdacoello

Answer 5

首先，你正在循环过多的数字。你不需要检查比给定数字小的每个数字是否是除数来检查一个数字是否为质数（我会让你自己想出为什么）。你正在运行数千亿次循环，而数以百万计的循环就足够了。

像这样的代码可以更快地运行，但并不是最优的：

    value=2
    for i in range(3, 2000000):
        prime=True 
        if i%2 != 0:
            for j in range(3, int(round(sqrt(i)+1)),2):
                if i % j==0:
                    prime=False
        else:
            prime=False
        if prime==True:
            value+=i
    print value

- Charles Dillon

Answer 6

你需要使用素数筛法来检查，可以尝试实现埃拉托色尼筛法。试除法在查找质数时非常低效，因为它的复杂度是n平方，运行时间增长非常快。此任务旨在教你如何寻找更好的方法。

- Pawel Miech

---

在厄拉托色尼筛法和一对一算法的优化方法之间，存在一个x140的因子。 - unddoch

Answer 7

当你使用埃拉托斯特尼筛法（链接）时，这个问题会非常快地给出输出。你可以通过一些修改使它更快，例如只考虑奇数并将整个200万数字迭代一半的方式。这样可以节省大量时间。

n = 2000000
ar = [False for x in range(n)]
sum = 2
def mul(a):
    i = 2;p = i*a
    while (p < n):
        ar[p] = 1
        ++i
        p = i*a
while (x < n):
    if(ar[x] == 0):
        sum += x;mul(x)
    x += 2
print (sum)

这里您可以看到相同的算法在C++中的实现：

#include<bits/stdc++.h>
using namespace std;
const int n = 2000000;
bool ar[n];
void mul(int a)
{
    int i = 2;int p = i*a;
    while(p < n)
    {
        ar[p] = 1;
        ++i;p = i*a;
    }
}
long long sieve()
{
    long long sum = 2;
    for(int i = 3;i < n;i += 2)
    {
        if(ar[i] == 0)
            sum += i,mul(i);
    }
    return sum;
}
int main()
{
    cout<<sieve();
    return 0;
}

C++在任何情况下都比Python快大约10倍，对于这个算法也是如此。

- lethal

---

我是一名初学者程序员，但我仍然不理解你的代码。这句话的意思是什么？ar = [False for x in range(n)] - smid_the_best

我也运行了你的代码，它说你在赋值之前引用了本地变量 x。 - smid_the_best

Answer 8

sum = 2

def isPrime(n):
    if n % 2 == 0: return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0: return False
    return True
if __name__ == "__main__":
    n = 1
    while n < 2000000:
        n += 2
        if isPrime(n):sum += n
print sum

- Amulya Acharya

Answer 9

import time
start = time.time()

def is_prime(num):
    prime = True
    for i in range(2,int(num**0.5)+1):
        if num % i == 0:
            prime = False
            break
    return prime
sum_prime = 0
for i in range(2,2000000):
    if is_prime(i):
        sum_prime += i
print("sum: ",sum_prime)

elapsed = (time.time() - start)
print("This code took: " + str(elapsed) + " seconds")

- jackson jones