PRINT - Prime Intervals

no tags 

In this problem you have to print all primes from given interval.

Input

t - the number of test cases, then t lines follows. [t <= 150]
On each line are written two integers L and U separated by a blank. L - lower bound of interval, U - upper bound of interval. [2 <= L < U <= 2147483647] [U-L <= 1000000].

Output

For each test case output must contain all primes from interval [L; U] in increasing order.

Example

Input:

2
2 10
3 7

Output:

2
3
5
7
3
5
7

hide comments
code0monkey1: 2018-02-17 16:45:56

really helpful video tutorial ( the tutorial is partially in Hindi , so it would be difficult for non-Hindi speaking people to understand what the presenter is saying ) based on this specific question : https://www.youtube.com/watch?v=fByR5N-TseY&t=650s

sanyam19: 2018-01-08 15:30:45

took 2 hrs... but finally done... :))
prime generator ka thda sa changed roop....
use sieve method....
=>[U-L <= 1000000]<= constraint (dont forget this)

captaindavinci: 2017-10-16 18:46:12

Why does Rabin Miller test with memoization not work for this problem? Isn't Rabin Miller a logarithmic computation with fast modular exponentiation.

kchiranjewee69: 2017-10-09 17:04:07

solved in 0.2second

vasilis: 2017-09-22 21:02:06

Anyone managed to run this with Java?

elegantalgo: 2017-06-25 04:37:31

Solved it in python! :D Execution time: 0.61 sec :D :D

Last edit: 2017-07-30 04:10:21
lucifer_786: 2017-06-18 12:46:21

Same as PRIME1 , just used fast i/o ;)

rohijulislam: 2017-06-03 08:07:20

For avoiding TLE
cout->printf
cin->scanf

hacker_sk: 2017-02-13 16:21:39

AC in 0.18 sec ... mine 15th position .. LOL just use fast i/o ans optimized segmented sieve :D

soodan: 2016-12-06 06:50:11

implement segmented sieve


Added by:Roman Sol
Date:2005-03-28
Time limit:1.223s
Source limit:15000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZCon