Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
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.
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.
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)
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);
}
}