10

我正在学习编程面试的要素，但我遇到了一个问题。它是关于编写一个 c++ 函数来查找从 1 到 n 的所有素数，对于给定的 n。

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;
    // is_prime[i] represents (2i+3) is prime or not

    vector<int> primes; // stores the primes from 1 to n

    primes.push_back(2);
    vector<bool> is_prime(size, true);

    for(long i = 0; i < size; ++i) {
       if(is_prime[i]) {
           int p = (i << 1) + 3;
           primes.push_back(p);
           // sieving from p^2, whose index is 2i^2 + 6i + 3
           for (long j = ((i * i) << 1) + 6 * i + 3; j < size; j += p) {
               is_prime[j] = false;
           }
       }
    }
}

特别是，我无法理解评论中的“从 p^2 筛选，其索引为 2i^2 + 6i + 3”部分。对于其他部分，我可以大致了解它们是如何工作的，但我不知道这个 '2i^2 + 6i + 3' 是从哪里来的，它是做什么的，以及它是如何工作的以及它的相关部分代码工作。

谁能更好地解释这段代码？谢谢你。

+

我得到这个输出（+'cout's 更好地理解它）

./a.out 100
size is: 49
for i = 0 is_prime[i] is 1
pushing back p of size 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 3
((i * i) << 1) + 6 * i + 3 for i of 0 is 6
((i * i) << 1) + 6 * i + 3 for i of 0 is 9
((i * i) << 1) + 6 * i + 3 for i of 0 is 12
((i * i) << 1) + 6 * i + 3 for i of 0 is 15
((i * i) << 1) + 6 * i + 3 for i of 0 is 18
((i * i) << 1) + 6 * i + 3 for i of 0 is 21
((i * i) << 1) + 6 * i + 3 for i of 0 is 24
((i * i) << 1) + 6 * i + 3 for i of 0 is 27
((i * i) << 1) + 6 * i + 3 for i of 0 is 30
((i * i) << 1) + 6 * i + 3 for i of 0 is 33
((i * i) << 1) + 6 * i + 3 for i of 0 is 36
((i * i) << 1) + 6 * i + 3 for i of 0 is 39
((i * i) << 1) + 6 * i + 3 for i of 0 is 42
((i * i) << 1) + 6 * i + 3 for i of 0 is 45
((i * i) << 1) + 6 * i + 3 for i of 0 is 48
for i = 1 is_prime[i] is 1
pushing back p of size 5
((i * i) << 1) + 6 * i + 3 for i of 1 is 11
((i * i) << 1) + 6 * i + 3 for i of 1 is 16
((i * i) << 1) + 6 * i + 3 for i of 1 is 21
((i * i) << 1) + 6 * i + 3 for i of 1 is 26
((i * i) << 1) + 6 * i + 3 for i of 1 is 31
((i * i) << 1) + 6 * i + 3 for i of 1 is 36
((i * i) << 1) + 6 * i + 3 for i of 1 is 41
((i * i) << 1) + 6 * i + 3 for i of 1 is 46
for i = 2 is_prime[i] is 1
pushing back p of size 7
((i * i) << 1) + 6 * i + 3 for i of 2 is 23
((i * i) << 1) + 6 * i + 3 for i of 2 is 30
((i * i) << 1) + 6 * i + 3 for i of 2 is 37
((i * i) << 1) + 6 * i + 3 for i of 2 is 44
for i = 3 is_prime[i] is 0
for i = 4 is_prime[i] is 1
pushing back p of size 11
for i = 5 is_prime[i] is 1
pushing back p of size 13
for i = 6 is_prime[i] is 0
for i = 7 is_prime[i] is 1
pushing back p of size 17
for i = 8 is_prime[i] is 1
pushing back p of size 19
for i = 9 is_prime[i] is 0
for i = 10 is_prime[i] is 1
pushing back p of size 23
for i = 11 is_prime[i] is 0
for i = 12 is_prime[i] is 0
for i = 13 is_prime[i] is 1
pushing back p of size 29
for i = 14 is_prime[i] is 1
pushing back p of size 31
for i = 15 is_prime[i] is 0
for i = 16 is_prime[i] is 0
for i = 17 is_prime[i] is 1
pushing back p of size 37
for i = 18 is_prime[i] is 0
for i = 19 is_prime[i] is 1
pushing back p of size 41
for i = 20 is_prime[i] is 1
pushing back p of size 43
for i = 21 is_prime[i] is 0
for i = 22 is_prime[i] is 1
pushing back p of size 47
for i = 23 is_prime[i] is 0
for i = 24 is_prime[i] is 0
for i = 25 is_prime[i] is 1
pushing back p of size 53
for i = 26 is_prime[i] is 0
for i = 27 is_prime[i] is 0
for i = 28 is_prime[i] is 1
pushing back p of size 59
for i = 29 is_prime[i] is 1
pushing back p of size 61
for i = 30 is_prime[i] is 0
for i = 31 is_prime[i] is 0
for i = 32 is_prime[i] is 1
pushing back p of size 67
for i = 33 is_prime[i] is 0
for i = 34 is_prime[i] is 1
pushing back p of size 71
for i = 35 is_prime[i] is 1
pushing back p of size 73
for i = 36 is_prime[i] is 0
for i = 37 is_prime[i] is 0
for i = 38 is_prime[i] is 1
pushing back p of size 79
for i = 39 is_prime[i] is 0
for i = 40 is_prime[i] is 1
pushing back p of size 83
for i = 41 is_prime[i] is 0
for i = 42 is_prime[i] is 0
for i = 43 is_prime[i] is 1
pushing back p of size 89
for i = 44 is_prime[i] is 0
for i = 45 is_prime[i] is 0
for i = 46 is_prime[i] is 0
for i = 47 is_prime[i] is 1
pushing back p of size 97
for i = 48 is_prime[i] is 0

这对我来说也没有意义。

例如，为什么对于 p=5，它从 11 开始，而不是 5^2 = 25，在下面的行中？推回大小为 5 的 p ((i * i) << 1) + 6 * i + 3 for i of 1 是 11

另外，11不是素数吗？这真的很令人困惑。请帮我。谢谢你。

4

4 回答 4

20

算法

您的主要生成器代码使用的算法称为“埃拉托色尼筛法”。通常，它会创建一个数字列表，并遍历该列表。当前数字的所有乘法都从列表中删除，剩余的数字是素数。

例如，让我们考虑[2,3,4,5,6,7,8,9,10,11,12,13,14,15]。我们遇到 2，所以我们从列表中删除所有偶数：

[2,3,5,7,9,11,13,15]

3 相同：

[2,3,5,7,11,13]

5, 7,11并且13在列表中没有乘法，所以我们什么都不删除并保留一个素数列表。

视觉示例

在此处输入图像描述

在此示例中（由 Wikipedia 提供），从列表中删除了所有 2、3 和 5 的乘法 - 2 的乘法被涂成粉红色，3 的乘法被涂成绿色，5 的乘法被涂成深蓝色。接下来将迭代 7，因此它被突出显示。深色数字是素数，浅色数字不是素数，灰色数字尚未达到净值。

代码中的优化

正如@BenJackson 所提到的，您的代码被优化了两次：

  • 首先，它只存储从 3 开始的奇数，因为我们知道偶数不是素数（2 除外）。
  • 其次，对于数字 p，它只是从 p² 开始筛选。这是正确的，因为如果n<pthenn*p的乘法被筛分时已经n被筛分。

这就是为什么神秘评论的原因：

// sieving from p^2, whose index is 2i^2 + 6i + 3

假设我们的算法已经到达向量中的第二项，因此i=2。有问题的数字是 5，因为索引i表示数字2i+3（第一次优化）。

我们应该筛除所有的5乘法25。表示的索引25是11，因为25=2*11+3。11, 16, 21, 26, ...在您的打印输出之后，它会删除与数字相对应的indices 25, 35, 45, 55, ..——我们要删除的所有 5 的奇数乘法。

您可以在Wikipedia或Wolfram MathWorld上阅读更多相关信息，这里有一个不错的javascript 在线演示。

于 2013-06-03T04:43:06.503 回答
8

素数表只存储从 3 开始的奇数（显然偶数不能是素数）。关系在int p = (i << 1) + 3或行中给出p = 2i + 3。现在解决这个问题i，得到i = (p - 3)/2. 现在i对应的是p^2什么？插入(2i+3)^2第二个公式并简化。现在你有了iforp^2方面的ifor p。

示例：假设i=1，因此该条目is_prime[i]是对素数p=2i+3或的测试p=5。所以是的，它是主要的。现在 seive（在别处解释）想要在 25 开始标记非素数。它需要知道i对应于 25 的内容。现在您可以简单地计算p*p然后将其插入i=(p-3)/2并得到j=11。代码跳过了那些中间步骤（如上所示）直接计算j=2i^2+6i+3和获取j=11。

于 2013-06-03T04:34:01.793 回答
1

像这样的行：

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;

...

for(long i = 0; i < size; ++i) {
   if(is_prime[i]) {
       int p = (i << 1) + 3;

是一个“hack”，因此可以通过迭代 0、1、2、3i和使用p相应的可能素数 3、5、7、9 等来迭代潜在的素数 3、5、7 等。

它是除此之外的基本初筛。

于 2013-06-03T04:34:41.790 回答
1

正如其他人所指出的，根据公式p = 2 i + 1， i映射数组位置，p映射这些数组位置表示的数字。如果在程序中明确保留i和p可能更容易考虑：

function primes(n)
    m := floor((n-1)/2)
    sieve := makeArray(0..m-1, True)
    i := 0; p := 3; ps := [2]
    while p * p <= n
        if sieve[i]
            append p to ps
            j := (p*p - 3) / 2
            while j < m
                sieve[j] := False
                j := j + p
        i := i + 1; p := p + 2
    while i < m
        if sieve[i]
            append p to ps
        i := i + 1; p := p + 2
    return ps

原始代码中j的奇怪公式是通过采用上面显示的j的公式并用i而不是p重写而形成的。

如果您对使用素数进行编程感兴趣，我的博客上有一篇文章，其中包括深入讨论这个确切的公式。

于 2013-06-03T15:40:51.170 回答