## 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
 ixodus: 2018-05-23 20:43:28 I have attempted it using Python, but with a pretty naive approach. http://www.spoj.com/submit/PRIME1/id=21714298 could someone please help me out? I'm getting a ' Time Limit Exceeded' error. The 2nd problem on this site for me :/ jeffselal: 2018-05-20 17:22:18 I am getting a seg fault Here is my source code http://www.spoj.com/submit/PRIME1/id=21693308 Any suggestions to get rid of this Last edit: 2018-05-20 17:38:59 mushusax: 2018-05-16 18:11:38 let m <= i <= n I initially would've looped to check divisibility between 2 and i / 2. Why does 2 and sqrt(i) work? Would it not be less accurate? anshuraj110: 2018-05-14 20:47:38 http://www.spoj.com/submit/PRIME1/id=21660203 This is my solution..its giving TLE ..please suggest what to do? optimus007: 2018-05-02 22:53:02 I am using segmented sieve with range using c++ stl but getting SIGABRT runtime error can anyone help.The code runs fine on ide. trunghieu99tt: 2018-05-01 04:44:00 Hint: You can see that prime numbers always satisfy the 6n+1 and 6n-1 conditions. So you can check a prime number by check if it is divisible by a number which satisfy 6n+1 or 6n-1 ( of course, first you should check if it is less than 6). thanhtc: 2018-04-29 03:28:47 Anyone can do this with Sieve of Eratosthenes ? To me it works but gets time limit.I use C++ Last edit: 2018-04-29 03:29:44 shyaam kumaraselvan: 2018-04-25 22:55:07 After years :/ 0.32 sec syfe: 2018-04-16 18:57:42 I'm having TLE. Can anyone help me,please? yemyelcee: 2018-04-10 15:58:36 What does runtime error NZEC mean?

 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