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

2013-03-13 22:12:29 roshin
the program works when i run[gcc] in my system.
but here its showing compilation error.can anyone help me on this.......

2013-03-13 22:12:29 Chitirala Nagendra Vijay Kumar
can any one help me improving my approach.. thanQ.. <snip>

Last edit: 2022-06-19 12:27:16

2013-03-13 22:12:29 capint
One of the error I encountered is forgetting the case when m = n. For people getting exceeded error, pay attention to the detail n-m<=100000.

2013-03-13 22:12:29 Believer
Can some one tell me what is wrong with this code??
<snip>

Last edit: 2022-06-19 12:26:20

2013-03-13 22:12:29 Megha Ramesh Chandra Mantri
Hey, i am getting time exceeded error. But i am not able to get how to optimize it

2013-03-13 22:12:29 Rahul
I am getting SIGSEGV(runtime) error although it is running well on my machine. can anyone help me with this error?

2013-03-13 22:12:29 Jorian
plz, tell me what's wrong with my code <snip>

Last edit: 2022-06-19 12:26:17

2013-03-13 22:12:29 edumandakh
nice solution

2013-03-13 22:12:29 Christian Scott
I've added input testing to make sure no weird tests are getting run and I've tested my output using (1,1), (3,5), (2,4) and loads of cases starting and ending on even numbers, prime numbers (including my last sifting prime), and of course I've run the obligatory (1000000000-100000,1000000000) and they all run perfectly and produce correct answers that I've verified using other prime number generators out there, but I still get WA. What could be the problem?

Edit: In complete desperation I even tried manually adding \n and \r\n instead of letting Console.WriteLine() pick its own default. Still WA.

Last edit: 2012-11-25 09:03:33

2013-03-13 22:12:29 Shubham Depp Bansal
#include
int main()
{
long long int i=0,j=0,k=0,m,n,a[1000000001];
EDIT: no code
}
This is my code.On compilation it is saying that i am using size of array very big.

Last edit: 2012-11-21 01:43:05