洛谷P3383 【模板】线性筛素数
2024-10-15 00:41:31
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[]; int prime(long long n)
{
p[] = ;
p[] = ;
for (long long i = ;i <= n;i++)
if (!p[i])
for (long long j = i * ;j <= n;j += i)
p[j] = ;
}
bool check(long long x)
{
if (p[x]) return ;
return ;
}
int main()
{
long long n, b,m;
scanf("%lld%lld", &n, &m);
prime(n);
for (long long i = ;i <= m;i++)
{
scanf("%lld", &b);
if (check(b)) cout << "Yes" << endl;
else cout << "No" << endl;
} return ;
}
最新文章
- AJAX学习随笔
- 嵌入式Linux驱动学习之路(十四)按键驱动-同步、互斥、阻塞
- 解决libcurl7.50.3在windows XP SP3 VC++ 6.0下编译报错 unresolved external symbol __imp__IdnToAscii@20 unresolved external symbol __imp__IdnToUnicode@20
- android开发之——获取相册图片和路径
- eclipse 下的 merge 是如何实现的
- vi/vim使用进阶: 剑不离手 – quickfix
- [Spark] Pair RDD常见转化操作
- 【Flex】读取本地XML,然后XML数据转成JSON数据
- 一次关于js事件出发机制反常的解决记录
- 关于React Native的那些坑
- Scrapy 1.4 文档 02 安装指南
- Jmeter接口测试实战-数据传递
- IP通信基础课堂笔记----简答题
- jenkins 使用Git 报错:SSL certificate problem: self signed certificate in certificate chain
- [转载]Tomcat部署与配置
- centos7 下载安装tomcat9
- PCL点云特征描述与提取(1)
- linux安装tmux
- 20155322 2016-2017-2 《Java程序设计》第7周学习总结
- iOS中URL的解码和转义问题
热门文章
- 58.com qiyi
- PostgreSQL的9.4已经发布(译)
- Android Framework层Power键关机流程(一,Power长按键操作处理)
- [Java Basics] Reflection
- Spring使用——切面编程AOP使用
- JSP EL表达式 与输入有关的内置对象
- 【转载】分享一些Qt学习资源,欢迎下载
- 转 C# DataTable 和List之间相互转换的方法
- MACOS无限试用Cornerstone的方法
- JAVA修饰符类型(public,protected,private,friendly)