Sphere Online Judge

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!


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.


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.


1 10
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
Time limit:6s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6

hide comments
2014-04-11 16:56:39 Lincoln Lee
2014-04-05 10:47:21 JOJO
How to remove run time error?
2014-04-05 04:14:59 Xavier
time limit exceed :(
2014-04-03 20:07:05 Mohan Bhambhani
My python code works perfectly on codechef and ideone but it shows time limit exceeded here...I am new to spoj please help me

Last edit: 2014-04-03 20:27:54
2014-03-31 07:06:24 Subrahmanya Venu Madhav Chitta
Such a good question it is...Wasted abt 3 hrs ... :(
2014-03-28 17:12:11 .::Lakshman::.
@Rahul Walkar RTE because of memory, read the problem statement once again, n can be up to 10^9 and you are allocating O(n) memory which is causing run time error you should learn about sieve, that might help.

Last edit: 2014-03-28 17:12:40
2014-03-24 06:11:25 mukthar ahamad
My code has run time error.how to rectify that.please help me.
2014-03-23 14:23:31 rodolfo
is there any special character i am missing ? every time i get WA, i have tryed pretty much any \n conbination, should i put \0 at the end or something ?
2014-03-17 09:23:54 Sourav Verma
every time time limit exceed :( :(
2014-03-17 06:27:23 foxly
6 seconds is a reasonable time limit for languages like C, but makes the problem impossible for bytecode-interpreted languages like PHP. The time limit also needs to be set high enough or the ranges set low enough that its practical to brute-force it. This is problem #2 out of *thousands* ...you can't seriously be expecting people to be implementing advanced prime-finding algorithms on the second challenge after "hello world" ... :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.