c++ - 埃拉托色尼筛 : bit wise optimized

Question

在网上搜索后，我了解到按位版本的埃拉托色尼筛法非常有效。问题是我无法理解它使用的数学/方法。

我一直忙的版本是这样的:

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

我理解的要点(如有错误请指正):

1. 第 1 行的语句检查数字是否为合数。
2. 第 2 行的语句将数字“n”标记为合数。
3. 程序正在将值 0 或 1 存储在 int 的位中。这往往会将内存使用量减少到 x/32。 (x 是如果使用 int 来存储 0 或 1 而不是像我上面的解决方案中那样使用的大小)

截至目前，我头脑中的要点:

1. 第 1 行中的函数如何运行。该函数如何确保数字是否为复合数。
2. LINE 2 中的函数如何设置位。
3. 我还了解到按位筛在时间上是高效的，因为出色地。是因为仅使用按位运算符还是其他因素也对此做出了贡献。

有什么想法或建议吗？

Answer 1

从技术上讲，代码中也存在错误:

无符号标志[MAX>>6]={0};

划分MAX到 64，但如果 MAX不是 64 的整数倍，数组少一个元素。

第 1 行:让我们把它拆开:

 (flag[n>>6]&(1<<((n>>1)&31)))

flag[n>>6] (n >> 6 = n / 64)给出保存 n / 2 位值的 32 位整数.

因为只有“奇数”数是可能的质数，所以除以 n两个人:(n>>1) .

1<<((n>>1)&31)给我们对应于 n/2 的位在 0..31 内-(& 31 确保它在“范围内”)。

最后，使用&将左侧的值与右侧的值组合。

因此，如果元素为 n，则结果为真位号 n modulo 32放。

第二行本质上是相同的概念，只是它使用了|=。 (或等于)设置倍数对应的位。