埃拉托斯特尼筛法（素数高效筛选）

╰半夏微凉° 2022-05-25 01:56 222阅读 0赞

# 一、素数定义 #

素数又称质数（prime number），指**所有大于1的数中只能被1和它本身整除的数**。

# 二、埃拉托斯特尼筛法（Sieve of Eratosthenes） #

## 1.算法的基本思想： ##

如果一个数是质数，那么它的倍数**肯定非质**，利用事先定义的线性表以打表方式标记非质，则剩下的数就是素数。

## 2.筛选过程： ##

![20180506090946963][]

# 三、算法实现 #

char *p_sieve=new char[num+1];
       memset(p_sieve,'1',num*sizeof(char)+1);   //预先置全部数为素数
       for(unsigned long i=2;i<=sqrt(num);i++)    //循环从4开始，2 3都是素数所以这样跳过没有问题
       {
           if(p_sieve[i]=='0')        //已经处理过的数跳过
               continue;
           for(unsigned long j=i*i;j<=num;j+=i)    //检测到素数，剔除它的倍数，质为非质
               p_sieve[j]='0';
       }

# 四、类实现 #

#include <iostream>
    #include<memory.h>
    #include<cmath>
    using namespace std;
    class CSieve
    {
    private:
            char *p_sieve;
            unsigned long num;                //numÊÇ×î´ó·¶Î§
            void Excute_Prime();
    public:
            CSieve(unsigned long n);
    
            void printPrime();
            ~CSieve();
    };
    CSieve::CSieve(unsigned long n)
    {
        num=n;
        p_sieve=new char[num+1];
        memset(p_sieve,'1',num*sizeof(char)+1);   //预先置全部数为素数
    
        Excute_Prime();
    }
    void CSieve::Excute_Prime()
    {
        for(unsigned long i=2;i<=sqrt(num);i++)    //循环从4开始，2 3都是素数所以这样跳过没有问题
        {
            if(p_sieve[i]=='0')        //已经处理过的数跳过
                continue;
            for(unsigned long j=i*i;j<=num;j+=i)    //检测到素数，剔除它的倍数，质为非质
                p_sieve[j]='0';
        }
    }
    void CSieve::printPrime()
    {
        for(unsigned long i=2;i<=num;i++)  
            if(i==2)
                cout<<i;
            else
                if(p_sieve[i]-'0')
                    cout<<" "<<i;
        cout<<endl;
    }
    CSieve::~CSieve()
    {
        delete p_sieve;
    }
    
    /******************************测试代码*****************************************/
    int main()
    {
        int txt_time;
        unsigned long n;
        cin>>txt_time;
        while(txt_time--)
        {
            cin>>n;
            CSieve one_solve(n);
            one_solve.printPrime();
        }
        return 0;
    }

# 五、敲下黑板 #

## 1）预先打表 ##

一般素数处理的题目都会预先告知数据的最大范围，这个时候就可以采用预处理打表的方法先行处理，输出的时候直接判定线性表的处理结果就可以了。

## 2）筛法应用 ##

埃拉托斯特尼筛法在针对**输出范围内的素数**或者**判定一个数是否为素数**都是有比较高效率的，方法都是上面贴的代码那样实现。

## 3）NYoj素数三元组 ##

相应的例题，做过NYoj上面的素数三元组，那个时候我用自己设计的一个筛法，可以看看,传送门:[点击打开链接][Link 1]

## 快三个星期没有发文章了，东西攒了很多QwQ，还是会加快效率的，渣油~ ##

[20180506090946963]: /images/20220525/1b0d218152064cc2afc993e0ed50fc1a.png
[Link 1]: https://blog.csdn.net/szu_crayon/article/details/79101682