洛谷P3383 【模板】线性筛素数 P3383 【模板】线性筛素数
-
- 256通过
- 579提交
- 题目提供者HansBug
- 标签
- 难度普及-
最新讨论
- Too many or Too few lines
- 样例解释有问题
- 请注意！！！1不是质数，所…
题目描述
如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内）
输入输出格式
输入格式：第一行包含两个正整数N、M，分别表示查询的范围和查询的个数。
接下来M行每行包含一个不小于1且不大于N的整数，即询问概数是否为质数。
输出格式：输出包含M行，每行为Yes或No，即依次为每一个询问的结果。
输入输出样例
输入样例#1：
100 5 2 3 4 91 97
输出样例#1：
Yes Yes No No Yes
说明
时空限制：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。
如果把bool数组换成其它类型的就会超时，可见当数据大时，一些细微的差别都能对结果产生很大的影响.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; long long n, m; bool p[10000010]; int prime(long long n) { p[0] = 1; p[1] = 1; for (long long i = 2;i <= n;i++) if (!p[i]) for (long long j = i * 2;j <= n;j += i) p[j] = 1; } bool check(long long x) { if (p[x]) return 0; return 1; } int main() { long long n, b,m; scanf("%lld%lld", &n, &m); prime(n); for (long long i = 1;i <= m;i++) { scanf("%lld", &b); if (check(b)) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }