SPOJ PRIME1 - Prime Generator(线性筛)
2018-06-21 06:51:23来源:未知 阅读 ()
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Example
Input: 2 1 10 3 5 Output: 2 3 5 7 3 5
Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)
Information
After cluster change, please consider PRINT as a more challenging problem.
这网站没法搜题??!!
这也太狗血了吧qwq。。。
算了说题,,
首先直接上线性筛是不行的。
但是考虑询问的$l,r$很小,所以我们可以依次枚举。
有一个非常重要的性质:对于一个合数$x$,其除$1$外最小的质因子$<= \sqrt{x}$,
然后每次判断只需要枚举到$sqrt(x)$就可以了。
感觉强上Miller-Rabin也行。。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int MAXN = 1e6 + 10, B = 31; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int prime[MAXN], vis[MAXN], tot = 0; void Pre() { for(int i = 2; i <= 1e5; i++) { if(!vis[i]) prime[++tot] = i; for(int j = 1; j <= tot && prime[j] * i <= 1e5; j++) { vis[i * prime[j]] = 1; if(!i % prime[j]) break; } } } int check(int x) { int limit = sqrt(x); if(x == 1) return 0; for(int i = 1; prime[i] <= limit; i++) if((x % prime[i]) == 0) return 0; return 1; } main() { Pre(); int qwq = read(); while(qwq--) { int x = read(), y = read(); for(int i = x; i <= y; i++) if(check(i)) printf("%d\n", i); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ Primer抄书笔记(二)——变量和基本类型(下) 2020-02-25
- C++ Primer 抄书笔记(二)——变量和基本类型(上) 2020-02-24
- C++ Primer 抄书笔记(一) 2020-02-20
- 【c++primer练习】 typedef与指针、常量和类型别名 2019-11-18
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash