SPOJ Problem Set (classical)

2. Prime Generator

Problem code: PRIME1

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)

Added by:	Adam Dzedzej
Date:	2004-05-01
Time limit:	6s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All except: NODEJS PERL 6

hide comments

2013-05-24 10:50:26 amitsingh749
time limit exceed why ....
in my system it is working fine with in sec

2013-05-20 08:56:48 coding
phewww!!! after so many tle..jst because i was taking numbers upto n/2...got AC when taking sqrt(n) :P :D

2013-05-16 05:10:01 Jaideep
i always get TIME LIMIT exceeded, but my compiler shows less time than 6 seconds.any help ?

2013-05-15 12:57:01 Mayank
.why the hell i am getting runtime error (SIGSEGV).......everytime...i have checkd that there is no array out of bound....

2013-05-13 20:25:19 Balázs
I'm always getting "time limit exceeded". I'm using C++ with vector at the beginning, then after I'm just using pure arrays, but I'm always getting this! :(

2013-05-13 19:42:34 ওয়াসী (Wasi)
@Kumar Gaurav SIGXFSZ is a sign that you output more than 33MB of data...
check this out:
http://www.spoj.com/forum/viewtopic.php?f=3&t=12042&p=38622&hilit=SIGXFSZ&sid=126bc48672a23d65f78d8321a3c44f9f#p38622

SPOJ Forum is a good place to solve this type of error

Last edit: 2013-05-22 07:55:38

2013-05-13 06:48:08 Kumar Gaurav
I also got this one time
runtime error (SIGSEGV)
How to resolve this error....

2013-05-13 06:46:31 Kumar Gaurav
I am getting this
SIGXFSZ...please explain this

2013-05-11 05:20:39 Mayank Bhura
for each of the invalid inputs, do we exit the method or re-accept it using do-while loops?
#java

2013-05-10 23:10:25 Amit Kumar Yadav
My code is working perfectly fine when I tested by providing the input file exactly in the format required. But I don't how would it work when I submit it. Please let me know, if I shall have the provision to provide the input through file or just keep it run-time.