4

欧拉计划的第十个问题：

10以下的素数之和为2 + 3 + 5 + 7 = 17。

求两百万以下的所有素数之和。

我发现了这个片段：

sieve = [True] * 2000000 # Sieve is faster for 2M primes
def mark(sieve, x):
    for i in xrange(x+x, len(sieve), x):
        sieve[i] = False

for x in xrange(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)

print sum(i for i in xrange(2, len(sieve)) if sieve[i])

在此处发布 ，运行 3 秒。

我写了这段代码：

def isprime(n):
    for x in xrange(3, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

sum=0;
for i in xrange(1,int(2e6),2):
    if isprime(i):
        sum += i

我不明白为什么我的代码（第二个）要慢得多？

4

4 回答 4

10

您的算法正在逐个检查从 2 到 N（其中 N=2000000）的每个数字的素数。

Snippet-1 使用了大约 2200 年前发现的 Eratosthenes算法。它不会检查每个数字，但是：

  • 对从 2 到 2000000 的所有数字进行“筛选”。
  • 找到第一个数字 (2)，将其标记为素数，然后从筛子中删除其所有倍数。
  • 然后找到下一个未删除的数字 (3)，将其标记为素数并从筛子中删除其所有倍数。
  • 然后找到下一个未删除的数字 (5)，将其标记为素数并从筛子中删除其所有倍数。
  • ...
  • 直到找到素数 1409 并从筛子中删除它的所有倍数。
  • 然后找到了直到 1414 ~= sqrt(2000000) 的所有素数并停止
  • 不必检查从 1415 到 2000000 的数字。所有没有被删除的也是素数。

因此，该算法产生了直到 N 的所有素数。

请注意，它不做任何除法，只做加法（甚至不做乘法，对于这么小的数字并不重要，但对于更大的数字可能）。时间复杂度是O(n loglogn)当你的算法接近时O(n^(3/2))（或O(n^(3/2) / logn)@Daniel Fischer 评论），假设除法的成本与乘法相同。

来自维基百科（上面链接）文章：

随机存取机模型中的时间复杂度为 O(n log log n) 操作，这是素数谐波级数渐近逼近这一事实的直接结果log log n。

（n = 2e6在这种情况下）

于 2012-02-10T23:30:53.077 回答
4

第一个版本预先计算范围内的所有素数并将它们存储在sieve数组中，然后找到解决方案只是将素数添加到数组中的简单问题。它可以看作是一种记忆形式。

第二个版本测试范围内的每个数字，看它是否是素数，重复之前计算已经完成的大量工作。

总之，第一个版本避免了重新计算值，而第二个版本一次又一次地执行相同的操作。

于 2012-02-10T19:17:13.017 回答
2

为了轻松理解差异，请尝试考虑每个数字将用作分压器的次数：

在您的解决方案中，当数字 2 将被测试为素数时，将为每个数字测试数字 2。您沿途传递的每个数字都将用作下一个数字的分压器。

在第一个解决方案中，一旦你跨过一个你永远不会回头的数字——你总是从你到达的地方向前移动。顺便说一句，一个可能且常见的优化是仅在标记为 2 之后才使用奇数：

mark(sieve, 2)
for x in xrange(3, int(len(sieve) ** 0.5) + 1, 2):
    if sieve[x]: mark(sieve, x)

这样，您只需查看每个数字一次并清除其所有乘法，而不是一次又一次地检查所有可能的除法器，并检查每个数字及其所有前任，并且该if语句可以防止您对以前的数字重复工作遭遇。

于 2012-02-10T19:28:49.757 回答
2

正如 Óscar 的回答所表明的那样，您的算法重复了很多工作。要查看其他算法节省了多少处理，请考虑以下修改版本的mark()andisprime()函数，它跟踪函数被调用的次数以及 for 循环迭代的总数：

calls, count = 0, 0
def mark(sieve, x):
    global calls, count
    calls += 1
    for i in xrange(x+x, len(sieve), x):
        count += 1
        sieve[i] = False

在使用这个新函数运行第一个代码后，我们可以看到它mark()在 for 循环中被调用了 223 次，总共进行了 4,489,006 次（约 450 万次）迭代。

calls, count = 0
def isprime(n):
    global calls, count
    calls += 1
    for x in xrange(3, int(n**0.5)+1):
        count += 1
        if n % x == 0:
            return False
    return True

如果我们对您的代码进行类似的更改，我们可以看到isprime()调用了 1,000,000（100 万）次 for 循环的 177,492,735（约 1.775 亿）次迭代。

计算函数调用和循环迭代并不总是确定算法为什么更快的决定性方法，但通常更少的步骤 == 更少的时间，并且显然您的代码可以使用一些优化来减少步骤数。

于 2012-02-10T19:35:49.990 回答