## 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.

hide comments
 gozubair: 2018-09-28 13:09:46 Now my codes runs 0.01 second but i am getting run time error?? reclu: 2018-09-28 12:54:05 See the input constraints! Queries are less than 10. No sieves required. Plain brute force checking till sqrt(n) works!! gozubair: 2018-09-28 06:20:38 My code still giving me tle plz guide me in python gozubair: 2018-09-27 19:28:24 I am not finding python's solution yet karate_25: 2018-09-24 01:21:10 I wanna know why i get a wrong answer , could I know how u test inputs , do u test it as a collection of input or every input separately ?!! julkas: 2018-09-23 15:41:35 @kire85 I have tested sieve-of-atkin from geeksforgeeks on ideone.com with your modification for limit=10**6 (without printing primes) with PyPy. It's very slow - 0.17s. My PyPy implementations of SE (sieve of Etatosthenes), OSE (odd sieve of Etatosthenes), SS (sieve of Sundaram) for limit=10**6 give 0.04s. For this problem I use precomputed primes below (10**9)**0.5 with non orthodoxal Sundaram algorithm and then sieve interval for each query (my PyPy time - 0.02s). You can make custom and random tests on ideone.com or https://www.spoj.com/problems/BACTERIA/. If you want good Python time you must optimize I/O also. Last edit: 2018-09-23 16:41:22 kire85: 2018-09-23 09:53:33 in c++ i get a 0.4 solution with first sieve-ing the primes below 32000 (sqrt of 1 000 000 000) and then using those primes with modolus to check if each number is prime in the range for each testcase. I have coded the same solution i python but TLE. i used https://www.geeksforgeeks.org/sieve-of-atkin/ as sieve. The python code as a flaw. It is missing r =r+1 in the last while loop. I have pointed this out in the comments. marcobw1: 2018-09-09 19:01:16 Use complexity O(n^2) , check up division until squared(n), it shall work y17prashant: 2018-09-09 09:05:55 using seive will cause lot of memory for very large numbers . Just read the question we have to only output the prime numbers simply go by traditional sqrt(n) method or use segmented seive. joe_erwaa: 2018-09-08 18:35:18 would anyone please tell me what sieve is? i'm new for SPOJ

 Added by: Adam Dzedzej Date: 2004-05-01 Time limit: 6s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6