SPOJ PRIME1 - Prime Generator(线性筛)

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
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有