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!

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)

Information

After cluster change, please consider PRINT as a more challenging problem.
Added by:Adam Dzedzej
Date:2004-05-01
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken

hide comments
2015-01-22 18:37:00 Abhimanyu Srivastava
i'm getting TLE using Sieve of erasthonesis algo
2015-01-22 02:23:59 Arpan Das
@Binayaka: Can you please tell me what your issue was?
2015-01-21 06:50:44 SHUBHAM GARG
how to decrease the time of your program...?
2015-01-18 15:11:40 KG
Is there a way to know which test case gave a wrong answer to my code? i am getting correct answer for every test case i tried!
2015-01-12 17:38:12 tyra
i m also getting time limit exceeded.............but it runs well on my pc compiler........if someone has any idea about it.....PLZ HELP
2015-01-09 13:36:42 Mailson Menezes
I can't get AC on this one and I don't know why. While generating my inputs using real (and big) primes downloaded from another website, I always get the right answer. So my algorithm is supposedly fine. But when I try it here I always get WA.

Is there any corner case that I should be aware of? Am my supposed to break the last line? What if a test case doesn't have any prime numbers, should I just print a line break (as any other test cases) or not print any data at all? No, I'm not considering 1 as a prime number.
2015-01-08 06:22:52 Mitch Schwartz
@Alvaro Leal: It doesn't matter. The input is piped from a file to stdin, and the output of your program is piped to a file.
2015-01-08 05:57:44 Alvaro Leal
Should the program start printing primes after each test case line is entered or only after all test case lines are entered?

To make myself clearer, which of the two output options presented below is expected?

OPTION 1
[I]2
[I]1 10
[I]3 5
[O]
[O]2
[O]3
[O]5
[O]7
[O]
[O]3
[O]5
[O]

OPTION 2
[I]2
[I]1 10
[O]2
[O]3
[O]5
[O]7
[O]
[I]3 5
[O]3
[O]5
[O]


Last edit: 2015-01-08 06:05:47
2015-01-06 14:57:54 Rahul Kumar
what should i do to optimize the code . i have tried both c and java...time limit exceeding in both..http://ideone.com/lm5djk
2015-01-06 05:11:39 Binayaka
Hi, can anybody tell me why I am getting WA here. https://ideone.com/4wTSQ9 . As can be seen, the result set is true. Is there as fail set? What do we print for a set that doesn't comply with the above given condition (1 <= m <= n <= 1000000000, n-m<=100000) ? Or is my code failing just because of whitespace issues?

NVM, found the issue. Got AC :)

Last edit: 2015-01-06 09:40:15
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.