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
guru_shreyansh: 2021-05-04 12:52:18

Solved in JAVA in 0.55 secs. With bufferedReader & Segmented Sieve.

4444: 2021-01-02 12:11:20

Thank You @i_m_chitti

i_0__0_i: 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^^"

i_am_chitti: 2020-07-25 15:36:29

Use segmented sieve. Don't use cout and cin.
Instead use printf and scanf

lone_coderrr: 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!!

ganjaboi: 2020-06-21 07:25:29

sieve of eratosthenes will work here or not
Please help

krishp: 2020-05-24 21:23:38

Unfortunately, I do not believe this is solvable in python. Even with optimized segmented sieve + stdin/stdout, you cannot print out all the answers in time. It takes 1.11 seconds just to print out the primes within the range(2147483647-10**6,2147483647) and with 149 other test cases, it just cannot be achieved in time.

=(Francky)=> https://www.spoj.com/ranks/PRINT/lang=PYTH%203.2.3
It's possible, a bit hard ; True.

Last edit: 2020-05-25 08:37:22
nra: 2020-04-11 18:41:47

"time limit exceeded" every time I run it :( though it runs fine in my machine! any pointers?
PS: I am using the sqrt method already!

deepamgupta: 2020-01-15 18:28:16

I'm getting TLE after applying Segemented Sieve but getting correct answer on my PC, what should I do to optimise?

Last edit: 2020-01-15 18:29:15
hetp111: 2019-09-29 07:37:25

(l/p)*p to find multiple of p in l to r.


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