首页 > 代码库 > 埃氏筛法

埃氏筛法

埃氏筛法,理解起来很好理解,就是在1~n这n个连续的数里面开始筛出合数,知道剩下全部为素数,大致流程如下:

第一步:能够确定1不是素数,所以将1筛出,剩下从2开始的数列

第二步:找到2为第一个素数,那么遍历这个数列,将2的倍数筛出,形成一个新的数列

第三步:找到下一个素数 x,此时 x = 3,那么再次遍历这个数列,筛出 x 的倍数,剩下的数再次形成一个新的数列

第四步:重复第三步,直到将所有合数筛出

代码如下:

#include <iostream>
#include <cstring>
#define N 1000005
using namespace std;

int a[N];//存放素数的数组a
int b[N];//数字对应表

main()
{
    int n;
    while( cin >> n )//输入查找上限
    {
        memset( a, 0 ,sizeof(a) );
        memset( b, 1 ,sizeof(b) );//下标对应数字为素数则为1,否则为0,全部初始化为1
        int t = 0;//记录素数个数的变量
        b[0] = 0; b[1] = 0;// 0、1不是素数
        for( int i(0); i <= n; i++ )// 遍历不大于n的所有数
        {
            if ( b[i] )//如果这个数为素数
            {
                a[t++] = i;
                for( int j = 2*i; j <= n; j += i )// 此时i为找到的一个素数,所有 i的倍数都不是素数
                    b[j] = 0;
            }
        }
        for( int i(0); i < t; i++ )
            cout << a[i] <<"\t";
        cout << endl << "小于" << n << "的数中,共有" << t << "个素数" <<endl;
    }
}

运行一下就知道,这个筛数法非常的好用,即使输入1e6也能在很短的时间之内筛完,并且开始输出,但是任然存在一个问题,我可不可以不用一直筛到 n?而是在筛到n之前,且完成了将所有合数筛出后就退出呢?

答案是可以的!根据埃氏筛法的结论,我只需要筛到小于√n的那一个素数就行了,至于为什么就不在赘述,既然有了这个结论,很容易就写出来代码

如下:

#include <iostream>
#include <cstring>
#define N 1000005
using namespace std;

int b[N];//数字对应表

main()
{
    int n;
    while( cin >> n )//输入查找上限
    {
        memset( b, 1 ,sizeof(b) );//下标对应数字为素数则为1,否则为0,全部初始化为1
        b[0] = 0; b[1] = 0;// 0、1不是素数
        for( int i(0); i*i <= n; i++ )// 遍历不大于n的所有数
            if ( b[i] )//如果这个数为素数
                for( int j = 2*i; j <= n; j += i )// 此时i为找到的一个素数,所有 i的倍数都不是素数
                    b[j] = 0;
        for( int i(0); i < n; i++ )
            if(  b[i] )
                cout << i <<"\t";
    }
}

两个代码,很明显前面一个会慢一点,但是我能在筛的同时取出素数,而后一个,应为没有遍历整个数组,所以还需要遍历一下整个b数组才能知道哪些是素数。

埃氏筛法