欧拉计划 #10 (Python)

本文介绍了欧拉计划 #10 (Python)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

为什么我的算法找出所有小于 200 万的素数之和这么慢?我是一个相当初级的程序员，这就是我想出的解决方案:

Why is my algorithm for finding the sum of all prime numbers below 2 million so slow? I'm a fairly beginner programmer and this is what I came up with for finding the solution:

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

有人可以帮我吗?谢谢！

Can someone please help me out? Thanks!

推荐答案

你的算法使用了试除法，非常慢.更好的算法使用埃拉托色尼筛法:

Your algorithm uses trial division, which is very slow. A better algorithm uses the Sieve of Eratosthenes:

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)

这应该会在不到一秒的时间内运行.如果您对使用质数编程感兴趣，我在我的博客中谦虚地推荐这篇essay.

That should run in less than a second. If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.