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

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

题目背景

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

题目描述

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

输入输出格式

输入格式

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

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

输出格式

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
100 5
2
3
4
91
97

输出样例#1:

1
2
3
4
5
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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}
--It's the end.Thanks for your read.--