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
Uday Shankar: 2013-03-13 22:12:29

For each number n there is some other number 'x' which is less than n.If you check until that number 'x' it is enough
Also you need not check with every odd number from 3 to 'x',if you check with primes between 3 to 'x' its enough.
I mean to say that if that number is not divisible by 3 we need not check divisibility by 9 and 15 again,they will anyway not be divisible.

Aakash Srivastava: 2013-03-13 22:12:29

@uday...then what do you suggest,i`ve run out of options,plz help

Last edit: 2011-09-22 05:20:30
Uday Shankar: 2013-03-13 22:12:29

@Aakash
do you really need to check the divisibility upto half the number

Aakash Srivastava: 2013-03-13 22:12:29

time limit exceeded,i have already removed the even numbers from being checked,and when checking for divisibility for a number,m checking uptil half that number,excludind the even numbers
What else should i do???

Mr.[T]: 2013-03-13 22:12:29

my program runs good on gcc but on spoj it gives runtime error(SIGSEGV)...any suggestions?

Abhijit: 2013-03-13 22:12:29

it is coming time limit exceeded..what should i do?

vipin: 2013-03-13 22:12:29

@pratik: Java sometimes has that problem on spoj.so before submitting the code on spoj, run it in ideone.com. Its another online judge and you can use it without any account.

Rohit: 2013-03-13 22:12:29

Tips from neone who got an AC using Python?? and who did not use the Sieve...

Hazem: 2013-03-13 22:12:29

sieve depend on the number of index of array but here when we enter number for examples 1000000000 thats so big to put index of array

joseph guichebarou: 2013-03-13 22:12:29

quick question... I am trying to do this problem in python. The high level description of my algorithm is for each number in the given range of the test case, to loop from 2 to sqrt of the current number looking for a factor. if a factor is not found then i know that the number is prime. i cache that number and if it is the first test case i print it. on subsequent test cases i check the cache to see if i've already computed the primes in the range of the current test case. the problem i am having is that i am getting a "time limit exceeded" error. i was certain that this algorithm was more efficient than i sieve. any suggestions? p.s. i also immediately skip over any even numbers

Last edit: 2011-08-28 20:04:38

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