优化后的Sieve of Eratosthenes筛法

之前写了Sieve of Eratosthenes筛法,但总觉得算法还不够好,因为我们为每个数都留了一个bit,而显然的,除了2以外的偶数都不可能是质数,那么如果我们只为奇数申请bit位来标记的话,效率应该有进一步的提升。

在原来的算法中,我们初始化时是这样的

初始化
Sieve of Eratosthenes筛法初始化

那么,我们真的需要把偶数放进来吗?

Why on earth we need even numbers while we pick primes
Why on earth do we need even numbers while we pick primes

继续阅读优化后的Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法是一种找质数的算法。我们知道,对于一个合数,那么它必定可以分解为两个质数相乘,比如21=3x7。那么我们也可以理解为,一个合数必定是一个质数的倍数,对于刚才的例子,21就是质数3的7倍(当然也可以说是质数7的3倍)。

那么我们求给定范围内的质数就可以利用这一点——先把所有的数列出来,然后从2开始,把所有数的倍数都去掉,这样我们就能留下给定范围内的质数了。举个例子,求42以内的所有质数,那么我们的算法大致上是这样操作的:

继续阅读Sieve of Eratosthenes筛法