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
Nurul Huda: 2015-08-16 19:06:33

Finally solved it after trying for couple of hours ! time 0.0 and memory 2.1 mb :D

LIveshell: 2015-08-12 12:42:43

Can anyone give me test cases...my submission shows WA...

Carlos: 2015-08-11 19:45:55

Prime function doesn't return INT ? @jshade

vivked: 2015-08-10 18:01:50

It always show time limit exceeded though it works on my system within the specified time limit

Last edit: 2015-08-10 18:02:32
prajal_5: 2015-08-09 18:22:57

can anyone tell me how to reduce the time complexity? I used sieve of Eratosthenes but still it's exceeding time limit! here is my code. <snip>

Last edit: 2022-06-19 12:20:55
sarathsnair: 2015-08-07 11:40:38

I used the segmented sieve concept, but how to initialize an array of 1000000000 with true value ? It always gives RunTime error - Out of memory exception

AbhiToChill: 2015-08-05 20:06:52

i keep geting runtime error (NZEC) but the code works perfectly on my system :/
am using python

wesleyhovick: 2015-07-27 23:43:12

The trick to hitting the time limit is researching and knowing the theory behind finding Prime numbers. Begin with a brute force method, which is obviously going to be too slow, and reduce it from there. Read up on the facts of a prime number > including the fact that every prime >= 5 can be expressed as 6k+-1 . Good luck!

Last edit: 2015-07-27 23:43:58
vivek keshore: 2015-07-27 11:30:44

For those who are struggling with Python. This problem is solvable using Python. I was able to get AC in 0.38 seconds using Python 2.7

Hint- Only Seg Sieve

Last edit: 2015-07-27 11:33:45
ahmed55: 2015-07-25 21:01:51

i have tried to solve this prob a lot of times every time i get time limit so guys just move on i even learned some of c becuz of this :D


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