首页 > 代码库 > Eratosthenes筛选法

Eratosthenes筛选法

Sieve of Eratosthenes

筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。

 

开始使用埃拉托斯特尼筛选法计算小于100000的素数。

埃拉托斯特尼筛选法是最为知名的产生素数的筛选法,适用于产生最小的N个素数。

该方法的唯一缺点是使用的存储空间大,可以进一步改进。

另外,该算法也不适用于计算某个范围内的全部素数。

C++版使用的标志是布尔标志,比起C语言版(用整数数组作为标识太浪费空间;用位运算逻辑太复杂,易出错),使用的空间上改进相当多,并且逻辑也十分简单。

这是一个基础程序,用到的时候可以拷贝修改加以利用。

程序如下:

 

#include <iostream>
#include <cmath>
using namespace std;
const int MAXN=100000;
bool sieveflag[MAXN]={false,false,true};

void esieve(bool sflag[],int n)
{
    //初始化
    for(int i=3;i<MAXN;i++)
    {
        sflag[i++]=true;
        sflag[i]=false;
    }
    //筛选
    int max=sqrt(n);
    for(int i=3;i<=max;i++)
    {
        if(sflag[i])
        {
            for(int j=i<<1;j<=n;j+=i)
            {
                sflag[j]=false;
            }
        }
    }
}
int main()
{
    esieve(sieveflag,MAXN);
    int num=0;
    for(int i=2;i<=MAXN;i++)
    {
        if(sieveflag[i])
        {

            ++num;
            cout<<num<<":"<<i<<endl;
        }
    }
    return 0;
}

 

Eratosthenes筛选法