PRINT - Prime Intervals

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

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

hide comments
2024-01-28 01:39:22
seg sieve check cp algorithms

Last edit: 2024-01-28 01:39:45
2023-06-08 18:49:25
very tight time limit, TLE with endl but AC with '\n'
2023-01-07 12:56:44
@deepamgupta, I wrote a solution in js-monkey and the only way to optimise was to output lines at once. i.e. instead of calling print() 1000 times, concatenate the string, and print() only once. this reduced the execution time by about 1 second.
2022-05-23 05:24:12
RE:( It's not wise to use array or vector.
2021-05-04 12:52:18
Solved in JAVA in 0.55 secs. With bufferedReader & Segmented Sieve.
2021-01-02 12:11:20 4444
Thank You @i_m_chitti
2020-11-09 06:59:40
@Roman Sol
dataset is weak
INPUT:
1
2147483647 2147483647
OUTPUT:
2147483647
this will cause overflow..but the overflow solution passes
RIP for "AC in one go" peeps^^"
2020-07-25 15:36:29
Use segmented sieve. Don't use cout and cin.
Instead use printf and scanf
2020-06-26 11:04:37
Easy peasy! AC in one go, used the idea of segmentation for finding primes in range L-R and set the upper bound to the sqrt of INT_MAX!!
2020-06-21 07:25:29
sieve of eratosthenes will work here or not
Please help
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.