时间戳

首页 > 解决方案 > EPI：生成素数的优化算法

python - EPI：生成素数的优化算法

问题描述

我目前正在使用 python 中的“编程面试要素”，并且在这部分卡住了。下面的代码生成最多为 n 的素数。解释相当缺乏，我没有数学背景来理解它。

我们可以通过从 p^2 而不是 p 中筛选 p 的倍数来提高运行时间，因为 kp 形式的所有数字，其中 k < p 已经被筛选掉。

代码如下：

def generate_primesII(n):

    if n < 2:
        return []

    size = (n - 3) // 2 + 1
    primes = [2]  # stores the primes from 1 to n

    # is_prime[i] represents (2i + 2) is prime or not
    # Initially set each to true. Then use sieving to eliminate nonprimes
    is_prime = [True] * size

    for i in range(size):
        if is_prime[i]:

            p = i * 2 + 3
            primes.append(p)

            # Sieving from p^2, where p^2 = (4i^2 + 12i + 9). The index in is_prime
            # is (2i^2 + 6i + 3) because is_prime[i] represents 2i + 3

            # note that we need to use long for j because p^2 might overflow
            for j in range(2 * i**2 + 6 * i + 3, size, p):
                is_prime[j] = False
    return primes

我的问题是：

  1. 他们是怎么想出尺寸公式的
  2. 他们说is_prime[i] represents (2i + 3) is prime or not.我不明白为什么2i + 3。
  3. 他们是怎么得到的p = i * 2 + 3
  4. 以下是什么意思Sieving from p^2, where p^2 = (4i^2 + 12i + 9). The index in is_prime is (2i^2 + 6i + 3) because is_prime[i] represents 2i + 3
  5. 为什么 j 的范围以 2 * i**2 + 6 * i + 3

大多数数字对我来说似乎相当随机

标签： pythonalgorithmprimes

解决方案

一个朴素的筛子实现会有一个is_prime数组，代表n我们要检查的所有数字。所以它的大小是n. 然后对于每个p，我们从开始2*p并将其标记为“非质数”，然后转到3*p、4*p、5*p等，将每个标记为“非质数”。例如，当 时p = 2，我们将 4、6、8、10、12 等标记为“非素数”。然后当p = 3我们将 6、9、12、15 标记为“非素数”时。

我建议你自己实现这个算法，以了解它是如何工作的，然后再继续实现。您正在查看的代码使用一些技巧来减少完成的工作。但是要了解这些技巧，您需要了解基本算法。

他们是怎么想出尺寸公式的

这来自解决我们将检查素数的最大数字n = i * 2 + 3在i哪里的公式。它为我们要测试的所有数字n的值提供了一个上限。i

他们是如何得到 p = i * 2 + 3

这允许我们只测试从 3 开始的奇数。请注意，偶数不是素数，因此我们可以使用这个公式轻松跳过它们。

以下是什么意思从 p^2 中筛选，其中 p^2 = (4i^2 + 12i + 9)。is_prime 中的索引是 (2i^2 + 6i + 3) 因为 is_prime[i] 代表 2i + 3

请注意，在我们的简单算法中，我们两次将 6 和 12 标记为“非素数”。我们显然在这里做了一些额外的工作。我们可以通过意识到，当我们确定每个小于 的素数时p，我们已经将所有小于的合数标记p^2为“非素数”，从而避免这种额外的工作p。

所以我们只需要从 atp^2而不是 at开始p。现在对于p = 2，我们像以前一样标记 4、6、8、10、12 等。但是对于p = 3，我们标记 9、12、15、18 等，避免将 6 标记为“非素数”的双重工作。对于这两个示例，避免的双重标记量非常小，但随着p变大，这种技术加起来显着提高了性能。

至于公式p^2 = (4i^2 + 12i + 9)，你可以从我们所说的乘法时的FOIL方法推导出来(2*i+3)*(2*i+3)。对于您的代码，这并不重要，因为如果您这样做p = 2*i + 3，那么您可以p*p直接计算而无需担心底层的代数操作。

为什么 j 的范围以 2 * i**2 + 6 * i + 3 开头

我们有p^2 = (4i^2 + 12i + 9)并且我们需要j在is_primewhere中找到索引p^2 = j * 2 + 3。我们将它们设置为相等并求解j。

推荐阅读