筛素数法

我们要求从1~max中间的所有素数。

首先举个例子比如我们要求max = 100即100以内的素数。首先最简单的做法是我们从2开始,将2的倍数的所有数都去掉,然后是三的倍数的所有数,直到100, 剩下的所有数都是素数了。当然这种办法会有很多重复计算,比如说10被2筛掉一次,也被5筛掉一次。那怎样减少这种重复计算呢。
上面这种办法使用的特性是一个素数的倍数一定不是素数。

我们还可以用另外一个特性,即每个合数必有一个最小素因子,根据每个最小素因子去访问合数就能防止合数被重复访问。以max = 10为例
从2 开始,2被放进结果中, 然后2*2 = 4 被排除flag[4] = false;
然后是3, flag[3] = true 所以3被放进结果中并排除3*2 = 6和3*3=9
然后是4,flag[4]是false,4不是素数,然后4*2 = 8 4*3 = 12被排除掉。
以此类推。
这些数还是有重复计算,比如说12会被4*3排除一遍,也会被6*2排除一遍,这种情况怎么办呢?因为4和2都是12的因子,但是我们只希望12被他的最小因子2排除掉,所以当我们发现i是2的倍数以后,我们就不再排除以i和比2更大的数的因子,因为这些因子最终会被2排除掉的。所以当i % prime[j] == 0,我们就停止排除直接i++从下一个开始,这样就省掉了重复计算了。

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s