之前写了Sieve of Eratosthenes筛法，但总觉得算法还不够好，因为我们为每个数都留了一个bit，而显然的，除了2以外的偶数都不可能是质数，那么如果我们只为奇数申请bit位来标记的话，效率应该有进一步的提升。
在原来的算法中，我们初始化时是这样的
Sieve of Eratosthenes筛法初始化
那么，我们真的需要把偶数放进来吗？
Why on earth do we need even numbers while we pick primes
Monthly Archives: January 2016
Sieve of Eratosthenes筛法
Sieve of Eratosthenes筛法是一种找质数的算法。我们知道，对于一个合数，那么它必定可以分解为两个质数相乘，比如21=3x7。那么我们也可以理解为，一个合数必定是一个质数的倍数，对于刚才的例子，21就是质数3的7倍（当然也可以说是质数7的3倍）。
那么我们求给定范围内的质数就可以利用这一点——先把所有的数列出来，然后从2开始，把所有数的倍数都去掉，这样我们就能留下给定范围内的质数了。举个例子，求42以内的所有质数，那么我们的算法大致上是这样操作的：