C++ 线性筛素数

今天要写一篇亲民的博客了，尽力帮助一下那些不会线性筛素数或者突然忘记线性筛素数的大佬。

众所周知，一个素数的倍数肯定不是素数（废话）。所以我们可以找到一个方法，普通的筛法（其实不算筛，普通的是判断一个数是不是素数）判断素数要从2循环到sqrt(这个数)（开跟符号不会打），但线性筛素数根据之前的素数直接就可以知道他后面的某个数是不是素数。一个素数的判断方法是：如果有一个比他小的数乘上某个数，等于他，那么这个数就不是素数。由此得知不是素数的数肯定有一个数可以被他整除（应该是这么说）。这样一直往下走，最小的一个肯定是素数（细节留给同学们斯烤）。于是我们从2开始，遇到素数就开始乘，一直到上限位置。中间遇到的所有数一定全都是合数（上面讲过了的），我们把合数标记为1，遇到标记是0的数就是质数，然后重复上一步操作（就是一直乘，直到上限位置）。

处理完之后，标记是0的数就是素数，注意特判，0和1不是素数。

这么一说感觉不难的样子，放个代码

#include<iostream>
#include<math.h>
using namespace std;
int a[10000005],b[10000005];
int main()
{
    int m,n,s;
    cin>>m>>n;
    b[0]=1;
    b[1]=1;//初始化
    s=sqrt(m);//到开跟就行，在大就没必要了（a如果放大，而且超过上线，假设最多要乘上b，越过开跟后的a都是大于b的，在那之前，b已经先和a相乘了，所以大于开跟的数就没必要看了）
    for(int i=0;i<n;i++)
    {
        cin>>a[i];//没用scanf（千古罪人啊）
    }
    for(int i=1;i<=s;i++)//顺手从1开始了，无伤大雅
    {
        if(b[i]==0)//这是一个素数
        {
            for(int j=i+i;j<=m;j+=i)//加上自己，注意开始位置是i+i，不然会把这个数标记成合数的。
            {
                b[j]=1;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        if(b[a[i]]==0)//最后判断，是0就是质数，是1就是合数。
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
    return 0; 
}

好了，线性筛就讲到这里，希望对大家有帮助。（这个文章没打QWQ）

原文链接: https://www.cnblogs.com/lichangjian/p/13090862.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/354427

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++ 线性筛素数

相关推荐