在 Python 中作为函数调用时埃拉托色尼筛法要慢得多

Question

我有两个代码块，我编写的这两个代码块都是为了应用埃拉托色尼筛法将所有素数相加到 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)

但是，拆分为检查素数的函数的代码块要慢得多。我终其一生都无法弄清楚这些代码块之间的区别是什么。我做错了什么？

Answer 1

您的第二个实现将列表 is_prime 保留为本地列表。在每次函数调用时，它 "restarts" 通过将列表初始化为 (n + 1) * [True].

进行计算

因此，通过重新启动工作，您基本上完成了使用第二个实现时工作量的 N 倍。

编辑：正如@Aaron 在评论中正确指出的那样，您对 print() 的调用也会使第二个版本变慢。

问题

总结起来存在以下问题：

使用函数的实现重新开始工作
第二个实现打印。第一个没有哪个明显更快
附带说明：您的 is_prime 列表与您的函数同名。这会在例如使用递归时造成麻烦。

改进

作为一个非常简单的改进，您可以尝试（重命名和）将 is_prime 列表移动到全局变量中。然后，当 is_prime(n) 使用列表中尚不存在的数字调用时，您扩展列表（例如 some_list += difference * [True]）并仅计算差值。

在 Python 中作为函数调用时埃拉托色尼筛法要慢得多

Sieve of Erosthenes much slower when called as function in Python

python

math

primes

sieve

python-3.x