2018年4月月赛 Day1 哥德巴赫猜想题解

题目背景

要想证明哥德巴赫猜想，首先需要知道足够大的素数。求一下试试吧！

题目描述

如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围[1,N]内）

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例#1：

输出样例#1：

Yes
Yes
No
No
Yes

说明

1<=N<=10000000，1<=M<=100000

样例说明：

N=100，说明接下来的询问数均属于[1,100]。

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

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

筛法求素数的板子题，没什么说的。

可类比Luogu P3383

代码：

#include<iostream>
#include<cstdio>
using namespace std;
bool ans[10000010]={false};
int n,m,x,t;
void set()
{
    cin>>n>>m;
    t=n>>1;
    ans[1]=true;
    for(int i=2;i<=t;i++)
    {
        if(ans[i]) continue;
        for(int j=i<<1;j<=n;j+=i) ans[j]=true;
    }
}
void solve()
{
    while(m--)
    {
        cin>>x;
        if(ans[x]) cout<<"No\n";
        else cout<<"Yes\n";
    }
}
int main()
{
    set();
    solve();
    return 0;
}