python - EPI : Optimized Algorithm for Generating Primes Numbers

Question

我目前正在使用 python 进行“编程面试的要素”，并且陷入了这一部分。下面的代码生成 n 以内的素数。解释相当缺乏，而且我没有数学背景来理解它。

We can improve run-time by sieving p's multiples from p^2 instead of p, since all numbers of the form kp, where k < p have already been sieved out.

代码如下:

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] 代表 (2i + 3) 是否是素数。我无法理解为什么 2i + 3。
3. 他们是如何得到p = i * 2 + 3
4. 以下内容是什么意思 从 p^2 进行筛选，其中 p^2 = (4i^2 + 12i + 9)。 is_prime中的索引是(2i^2 + 6i + 3)，因为is_prime[i]代表2i + 3
5. 为什么 j 的范围以 2 * i**2 + 6 * i + 3 开头

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

Answer 1

这里有两个同时完成的关键技巧。我相信，这就是您感到困惑的主要原因。第一个是关于筛算法进展的数学事实。 (即从 p<sup>2</sup> 开始更新)另一个是通过不存储任何 is_prime 来使用更少空间的技巧。偶数数据)

让我们从您的前两个问题开始。 (2 * i + 3) is_prime[i] 中使用的映射似乎是一种空间优化，将使用的空间减少一半。 (即 is_prime 列表中不表示偶数)映射有助于仅迭代从 3 开始到 size 的奇数列表。 。如果你真的替换了 i变量 (2i + 3)初始值为size ，你会看到你最终得到 n 。 (或 n-1 ，取决于 n 是偶数还是奇数)

你的第三个问题相对更简单。在外循环中，i迭代奇数整数空间，直到 n 。因为有 (2i + 3) 的映射在is_prime , p被赋予该值。从那时起，p表示要在内循环中使用的实际质数。

第四个问题中的评论只是进一步解释了从 p<sup>2</sup> 开始迭代的数学思想。 。由于循环构成i成为映射(到实际值)p<sup>2</sup> 的一部分进一步用该变量 i 来表示。我认为该评论试图表达 2 * i**2 + 6 * i + 3 的使用初始化 j 的范围，但还很不清楚。

为了回答你的最后一个问题，我们应该考虑什么 j实际上代表。 j表示要更新的奇数个空间。与 i 的循环类似, j不会迭代实际值，而是迭代奇数。初始值为j是 2 * i**2 + 6 * i + 3 ，因为当您将该值替换为 i 时变量 (2*i + 3) (即从奇数空间到实际值集合的映射)，您将获得 4 * i**2 + 12 * i + 9 ，即p<sup>2</sup> .

内部循环基本上是分配 is_prime[j]=False到代表实际质数值的倍数的所有单元格 p ，从代表值 p<sup>2</sup> 的那个开始.