SPOJ.com - Problem PRIME1

PRIME1 - Prime Generator

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.

Submit solution!

Added by:	Adam Dzedzej
Date:	2004-05-01
Time limit:	6s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS PERL6

hide comments

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
what should i do to optimize the code . i have tried both c and java...time limit exceeding in both..<snip>

Last edit: 2022-06-19 12:40:02

2015-01-06 05:11:39 Binayaka
Hi, can anybody tell me why I am getting WA here. <snip> . 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: 2022-06-19 12:39:57

2015-01-05 22:23:27 Samuel
My solution gets runtime error (SIGSEGV)
please help ... this runs successfully at ideone <snip>

Last edit: 2022-06-19 12:39:48

2015-01-03 16:16:45 Sarjil Shariar
I don't understand where is the mistake in my code??