3

为什么我的算法找到所有低于 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

有人可以帮我吗？谢谢！

4

9 回答 9

6

您的算法使用试除法，这非常慢。更好的算法使用埃拉托色尼筛法：

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)

这应该在不到一秒钟的时间内运行。如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。

于 2013-08-14T12:52:18.663 回答
5

您可以进行许多优化（并且应该进行，因为您将需要为 Euler 项目中的许多问题生成质数，因此快速实现可以简化以后的事情）。

看看 Atkin 的筛子（和相关的筛子）（http://en.wikipedia.org/wiki/Sieve_of_Atkin），了解如何通过蛮力（算法上就是）加速素数生成。

然后看看这个 SO-post（列出 N 以下所有素数的最快方法）的精彩答案，它记录了许多素数生成算法/实现。

于 2013-07-08T10:56:03.470 回答
3

没有人指出这一点，但range在 Python 2.x 中使用非常慢。使用xrangeinstaed，在这种情况下，这应该会给您带来巨大的性能优势。
看到这个问题。

此外，您不必循环直到您检查的数字，检查直到round(sqrt(n)) + 1足够。（如果大于其平方的数字将它整除，那么您一定已经注意到有一个小于平方的数字。）

于 2013-07-08T11:29:32.380 回答
1

首先，你循环了太多的数字。你不需要检查每个小于给定数字的数字是否是除数来检查一个数字是否是素数（我会让你弄清楚为什么这是你自己）。您正在运行数千亿个循环，而数亿将在其中执行。

像这样的东西工作得更快，但绝不是最佳的：

    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
于 2013-07-08T10:52:34.293 回答
1

您需要使用prime sieve 查看eratostheneses sieve 并尝试在代码中实现它。

试除法对于寻找素数非常低效，因为它的复杂度为 n 平方，运行时间增长非常快。此任务旨在教您如何找到更好的东西。

于 2013-07-08T10:57:42.100 回答
1

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

  • 有一个函数可以为您提供下一个素数并临时将控制权返回给调用者。此类函数称为GENERATORS。
  • 要定义生成器函数，只需使用yield命令而不是return.
  • 当您使用 generators 时，就像知道该函数将被再次调用，并且当它发生时，函数内部的执行会在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)
于 2018-01-05T07:00:51.647 回答
0

当您使用 sieve of eratosthenes Link to it时，此问题的输出速度非常快。您可以通过一些修改使其更快，例如仅考虑奇数将整个 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 倍左右，对于这个算法也是如此。

于 2015-05-08T06:46:27.857 回答
0 
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
于 2016-05-06T07:37:15.037 回答
0 
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")
于 2018-07-02T10:46:01.027 回答