c - 欧拉计划问题 10 - 高效算法

Question

我使用非常简单的算法尝试了 Project Euler 的问题 10，运行时间看起来像几个小时。所以我搜索了一个有效的算法，并通过 Shlomif Fish 找到了这个。 .
代码复制如下:

int main(int argc, char * argv[])
{
    int p, i;
    int mark_limit;
    long long sum = 0;

    memset(bitmask, '\0', sizeof(bitmask));
    mark_limit = (int)sqrt(limit);

    for (p=2 ; p <= mark_limit ; p++)
    {
        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            /* It is a prime. */
            sum += p;
            for (i=p*p;i<=limit;i+=p)
            {
                bitmask[i>>3] |= (1 << (i&(8-1)));
            }
        }
    }
    for (; p <= limit; p++)
    {
        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            sum += p;
        }
    }

我在理解代码时遇到问题。具体来说，这个位移代码如何能够确定一个数字是否是素数。

   if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            /* It is a prime. */
            sum += p;
            for (i=p*p;i<=limit;i+=p)
            {
                bitmask[i>>3] |= (1 << (i&(8-1)));
            }
        }

谁能给我解释一下这个代码块，尤其是这部分 ( bitmask[p>>3]&(1 << (p&(8-1) ?非常感谢你。

Answer 1

该代码是经过修改的埃拉托色尼筛法。他正在将一个数字打包成一位:0 = 素数，1 = 复合。位移是为了到达字节数组中的正确位。

 bitmask[p>>3]

相当于

 bitmask[p / 8]

在 bitmask[] 中选择正确的字节大批。

(p&(8-1))

等于 p & 7 ，它选择 p 的低 3 位.这相当于 p % 8
总的来说，我们选择位 (p % 8)字节数 bitmask[p / 8] .那就是我们选择 bitmask[] 中的位。表示数字 p 的数组。
1 << (p % 8)设立 1位正确地位于一个字节中。然后将其与 bitmask[p / 8] 进行“与”运算byte 以查看该特定位是否已设置，从而检查是否 p是一个素数。

整个语句等于 if (isPrime(p)) ，使用已经完成的筛子部分来帮助扩展筛子。