Bil*_*ard 13
我认为这样做的方法是不要像我们通常那样将bitset视为其数值表示,而是将其视为数字列表.所以bitset
1111
将代表数字1,2,3和4.现在,如果我们说'1'代表素数而'0'代表素数,我们可以如下筛选.
将所有位设置为1(我将使用16位代表整数1到16)
1111 1111 1111 1111
我知道一个不是素数,所以我把它设置为零.
0111 1111 1111 1111
现在,我知道我遇到的下一个'1'代表一个素数,但是根据定义,该数字的所有倍数都不是素数,所以我单独留下下一个'1',但将其所有倍数设置为'0'.由于下一个'1'代表数字2,因此每隔一位I为零.
0110 1010 1010 1010
这种方法优于其他方法的好处是,当我遍历其余的位时,我不需要检查每个位以查看它是否可以被2整除(因此没有if i % 2 == 0必要).我可以继续将指数递增2,我知道我将永远落在非素数上.
现在我只是在我遇到的下一个"1"时再次做同样的事情(从我确定的最后一个素数开始的下一个素数,2).我知道这是最好的,因为它不能被它下面的任何数字整除.我知道它的所有倍数都是素数,因此它处于第三位,我将后面的每三位设置为'0'.其中一些已经是'0',因为它们也是2的倍数.那没关系,只需将它们保留为0即可.
0110 1010 0010 1000
你遇到的下一个'1'是第五位.现在你可以继续前进,直到你到达终点,但由于5大于我开始时的位数的平方根,我知道我不会再找到任何复合材料,所以我已经完成了.
经过一番搜索后,我在Deitel&Deitel的C++ How to Program中找到了一个非常好的实现示例.它们还提供了对算法和代码的良好解释.