在我的教科书中无法理解这个素数生成器算法

Question

我正在研究编程访谈的元素,我遇到了问题.它是关于编写一个c ++函数,用于查找给定n的从1到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的评论'sieving,其索引是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,i为1为11

还有,11不是素数？这真的令人困惑.请帮我.谢谢.

Answer 1

算法

您的素数生成器代码使用的算法称为"Eratosthenes的筛选".通常,它会创建一个数字列表,并在列表上进行迭代.从列表中删除当前数字的所有乘法,其余数字为素数.

例如,让我们考虑一下[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在列表中没有乘法,所以我们删除任何和保持与质数的列表.

视觉例子

在这个例子中(由维基百科提供),2,3和5的所有乘法都从列表中删除 - 2的乘法绘制为粉红色,3的乘法绘制为绿色,乘以5为深蓝色.接下来将重复7,因此它会突出显示.深色数字是素数,浅色数字不是素数,灰色数字已达到净值.

代码中的优化

如@BenJackson所述,您的代码优化了两次:

• 首先,它只存储从3开始的奇数,因为我们知道偶数不是素数(2除外).
• 其次,对于数字p,它只能从p²开始筛选.这是正确的,因为如果n<p那时n*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, ...与数字相对应的索引25, 35, 45, 55, ..- 我们想删除的所有奇数乘法都是5.

您可以在Wikipedia或Wolfram MathWorld上阅读更多相关信息,这里有一个很好的javascript在线演示.

Answer 2

素数表只存储从3开始的奇数值(显然,偶数值不能是素数).关系在行中给出int p = (i << 1) + 3,或者p = 2i + 3.现在解决了i,让i = (p - 3)/2.现在i对应的是p^2什么？插入(2i+3)^2第二个公式并简化.现在你有ifor p^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.