python中小于2,000,000的素数总和 [英] Sum of primes below 2,000,000 in python

问题描述

我正在尝试欧拉计划的问题 10，它是所有 2,000,000 以下素数的总和.我曾尝试使用 Python 实现 Erasthotenes 筛分法，我编写的代码非常适合 10,000 以下的数字.

I am attempting problem 10 of Project Euler, which is the summation of all primes below 2,000,000. I have tried implementing the Sieve of Erasthotenes using Python, and the code I wrote works perfectly for numbers below 10,000.

但是，当我尝试为更大的数字求素数的总和时，代码运行时间太长(找到最多 100,000 的素数总和需要 315 秒).该算法显然需要优化.

However, when I attempt to find the summation of primes for bigger numbers, the code takes too long to run (finding the sum of primes up to 100,000 took 315 seconds). The algorithm clearly needs optimization.

是的，我看过这个网站上的其他帖子，比如 列出 N 下所有质数的最快方法，但是那里的解决方案对代码的工作原理几乎没有解释(我仍然是一个初学者程序员)所以我无法真正向它们学习.

Yes, I have looked at other posts on this website, like Fastest way to list all primes below N, but the solutions there had very little explanation as to how the code worked (I am still a beginner programmer) so I was not able to actually learn from them.

有人可以帮我优化我的代码，并清楚地解释它是如何工作的吗?

Can someone please help me optimize my code, and clearly explain how it works along the way?

这是我的代码:

primes_below_number = 2000000 # number to find summation of all primes below number
numbers = (range(1, primes_below_number + 1, 2)) # creates a list excluding even numbers
pos = 0 # index position
sum_of_primes = 0 # total sum
number = numbers[pos]
while number < primes_below_number and pos < len(numbers) - 1:
    pos += 1
    number = numbers[pos] # moves to next prime in list numbers
    sum_of_primes += number # adds prime to total sum
    num = number
    while num < primes_below_number:
        num += number
        if num in numbers[:]:
            numbers.remove(num) # removes multiples of prime found

print sum_of_primes + 2

正如我之前所说，我是编程新手，因此对任何复杂概念的详尽解释将不胜感激.谢谢.

As I said before, I am new to programming, therefore a thorough explanation of any complicated concepts would be deeply appreciated. Thank you.

推荐答案

如您所见，有多种方法可以在 Python 中实现比您的代码更高效的 Erasthotenes 筛法.我不想用花哨的代码迷惑你，但我可以展示如何加快你的代码速度.

As you've seen, there are various ways to implement the Sieve of Erasthotenes in Python that are more efficient than your code. I don't want to confuse you with fancy code, but I can show how to speed up your code a fair bit.

首先，搜索列表并不快，从列表中删除元素甚至更慢.然而，Python 提供了一个 set 类型，它在执行这两个操作时非常有效(尽管它确实比简单的列表消耗更多的 RAM).令人高兴的是，修改您的代码以使用集合而不是列表很容易.

Firstly, searching a list isn't fast, and removing elements from a list is even slower. However, Python provides a set type which is quite efficient at performing both of those operations (although it does chew up a bit more RAM than a simple list). Happily, it's easy to modify your code to use a set instead of a list.

另一个优化是我们不必一直检查质因数直到 primes_below_number，我在下面的代码中将其重命名为 hi.只求hi 的平方根就足够了，因为如果一个数是合数，它的因数必须小于或等于它的平方根.

Another optimization is that we don't have to check for prime factors all the way up to primes_below_number, which I've renamed to hi in the code below. It's sufficient to just go to the square root of hi, since if a number is composite it must have a factor less than or equal to its square root.

我们不需要保留质数总和的运行总和.最后最好使用 Python 的内置 sum() 函数，该函数以 C 速度运行，因此比以 Python 速度逐个加法要快得多.

We don't need to keep a running total of the sum of the primes. It's better to do that at the end using Python's built-in sum() function, which operates at C speed, so it's much faster than doing the additions one by one at Python speed.

# number to find summation of all primes below number
hi = 2000000

# create a set excluding even numbers
numbers = set(xrange(3, hi + 1, 2)) 

for number in xrange(3, int(hi ** 0.5) + 1):
    if number not in numbers:
        #number must have been removed because it has a prime factor
        continue

    num = number
    while num < hi:
        num += number
        if num in numbers:
            # Remove multiples of prime found
            numbers.remove(num)

print 2 + sum(numbers)

你应该会发现这段代码运行了几秒钟；在我的 2GHz 单核机器上大约需要 5 秒.

You should find that this code runs in a a few seconds; it takes around 5 seconds on my 2GHz single-core machine.

您会注意到我已经移动了评论，以便它们位于评论所在的行上方.这是 Python 中的首选样式，因为我们更喜欢短行，而且行内注释往往会使代码看起来很混乱.

You'll notice that I've moved the comments so that they're above the line they're commenting on. That's the preferred style in Python since we prefer short lines, and also inline comments tend to make the code look cluttered.

可以对内部 while 循环进行另一个小的优化，但我让您自己解决.:)

There's another small optimization that can be made to the inner while loop, but I let you figure that out for yourself. :)

这篇关于python中小于2,000,000的素数总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！