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
2016-07-21 23:51:38 Shidhu
ACCC at 0.74 by Segmented Sieve :)
2016-05-27 09:54:12
cout->printf
cin->scanf
That's all I needed to change in the sol prime1 to get AC, This was fun :P
2016-05-06 08:45:38
Accepted!! Exactly same code as of PRIME1. I see a 0.46s more time.
0.51s 3.3M C++14
2016-03-31 22:44:16
lolypop after prime generator
2015-12-29 20:30:50
@Roman sol
please check the program
i still not getting why it is giving tle
though it is well compiled in prime1.
i already checked for many test cases
submission id=15968606
2015-11-19 07:56:36
My code passed and gave the correct output in ideone.com
But here, it shows sigsegv error!
Can someone help me?
2015-10-30 08:24:22
Hi, just a quick question. My solution can solve a single (worst) test case in 0.02s but times out at the test. Does it mean that it should pass 150 tests in less than 1.2sec?
Thanks!
Edit: Just changed cout to printf and finished in 0.3sec, watch out for it!

Last edit: 2015-10-31 10:21:41
2015-10-29 20:05:42 bholagabbar
C++ with Segmented Sieve passes in 0.62. Same solution in JAVA times out.

Last edit: 2015-10-29 21:38:24
2015-10-25 20:51:43 asshole
i got a tle problem
tried implementation in c++ using seg. sieve as i know it can anyone help me ?
submission id . 15466645
2015-10-21 14:49:08 Aditya Kumar
Learned Seg. Seive. Also enjoyed reducing TLE -> WA -> AC :)

Last edit: 2015-10-21 14:49:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.