使用位阵列筛选埃拉托色尼

Question

我有一个< code >无符号int的位数组< code>prime[]。我希望用这个数组实现一个厄拉多塞筛，让每一位代表一个数。也就是说，给定< code>n，保存对应于< code>n的位的数组元素将是< code>prime[n/32]，并且特定位将在位置< code>n2中。

我的testBitIs0（int n）函数在数字为素数时返回1（如果其位==0），否则返回0：

return ( (prime[n/32] & (1 << (n%32) )) != 0);  

我的< code>setBit(int n)函数只是将相应位置的位设置为1:

int i = n/32;
int pos = n%32;
unsigned int flag = 1;
flag = flag << pos;
prime[i] = prime[i] | flag;

我遇到的问题是，当我用素数的倍数调用setBit时，我认为它没有正确设置位。当我下次运行此行时，用素数的倍数调用setBit时（例如数字2的4、6、8等）：

if(testBitIs0(i)) { ... }

当 i = 4/6/8/等时，当它应该返回 0 时，它仍将返回 1。
有人可以检查我的代码以确保我正确实现了这一点吗？谢谢。

Answer 1

这看起来像是在做你所追求的。还有一个位数组和一些位闪烁函数。

http://bcu.copsewood.net/dsalg/bitwise/bitwise.html