在Python中，将埃拉托斯特尼筛法作为函数调用会慢得多

Question

在Python中，将埃拉托斯特尼筛法作为函数调用会慢得多

3

我有两段代码，都是用埃拉托色尼筛法来求解到2000000的所有质数之和。第一段代码是原始代码，没有包装在任何函数中，如下所示：

N = 2000000
is_prime = (N + 1) * [True]

for candidate in range(2, N + 1):
    if is_prime[candidate]:
        print(candidate)
        for witness in range(2 * candidate, N + 1, candidate):
            is_prime[witness] = False

第二段代码将这个功能拆分成一个检查质数的函数和一个指定上限的for循环。代码如下：

  def is_prime(n):
  is_prime = (n + 1) * [True]

  for candidate in range(2, int(sqrt(n)) + 1):
      if is_prime[candidate]:
          for witness in range(2 * candidate, n+1, candidate):
              is_prime[witness] = False

  return is_prime[n]

for candidate in range(2, LIMIT):
    if is_prime(candidate):
        print(candidate)

然而，拆分成检查素数的函数的代码块速度无限慢。我一直无法弄清这些代码块之间的差异。我做错了什么吗？

- EthanS

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Flurin · Accepted Answer

您的第二个实现将列表is_prime保留为本地变量。在每次函数调用时，它通过将列表初始化为(n + 1) * [True]来“重新启动”计算。

因此，通过重新启动工作，您基本上会在使用第二种实现时做N倍的工作。

编辑：正如@Aaron在评论中正确指出的那样，您对print（）的调用也使第二个版本变慢。问题总结一下，存在以下问题：

- 使用函数的实现重新启动其工作 - 第二个实现执行打印操作。第一个不执行，显然更快。 - 只是作为附注：您的is_prime列表与函数同名。例如，在使用递归时，这将会引起麻烦。改进作为非常简单的改进，您可以尝试将is_prime列表（重命名并）移动到全局变量中。然后，当使用尚未在列表中的数字调用is_prime（n）时，您会扩展列表（例如some_list += difference * [True]），并且只计算差异。