首页 > 代码库 > 洛谷 P3383 【模板】线性筛素数

洛谷 P3383 【模板】线性筛素数

P3383 【模板】线性筛素数

题目描述

如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

输入输出格式

输入格式:

 

第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。

接下来M行每行包含一个不小于1且不大于N的整数,即询问概数是否为质数。

 

输出格式:

 

输出包含M行,每行为Yes或No,即依次为每一个询问的结果。

 

输入输出样例

输入样例#1:
100 52349197
输出样例#1:
YesYesNoNoYes

说明

时空限制:500ms 128M

数据规模:

对于30%的数据:N<=10000,M<=10000

对于100%的数据:N<=10000000,M<=100000

样例说明:

N=100,说明接下来的询问数均不大于100且大于1。

所以2、3、97为质数,4、91非质数。

故依次输出Yes、Yes、No、No、Yes。

 

/*素数筛 模板*/#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int read(){    int x=0,f=1;char ch=getchar();    while (ch<0 || ch>9)    {        if(ch==-)            f=-1;        ch=getchar();    }    while (ch>=0 && ch<=9)    {        x=x*10+ch-0;        ch=getchar();    }    return x*f;}const int mxn=10000005;int pri[mxn*2],cnt;bool vis[mxn];void PRI(int mxn){    vis[1]=1;    int i,j;    for (i=2;i<mxn;i++)    {        if (!vis[i])            pri[++cnt]=i;        for (j=1;j<=cnt && i*pri[j]<mxn;j++)        {            vis[i*pri[j]]=1;            if (i%pri[j]==0)                break;        }    }    return;}int n,m;int main(){    n=read();    m=read();    PRI(n+3);    int x;    while (m--)    {        x=read();        if (vis[x])            printf("No\n");        else             printf("Yes\n");    }    return 0;}

 

洛谷 P3383 【模板】线性筛素数