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 Thang Do
result: success time: 0.04s memory: 37984 kB returned value: 0

input:
2
1000 2000
100 200

This is what I get from Ideone.com
But I still encounter runtime error SIGKILL from SPOJ ?

Is it because I didnt specify the input for SPOJ?

Need help, please

2013-03-13 22:12:29 Andrew
I don't think this can be done in Ruby unless you just build a giant prime container and pull primes out of it instead of calculating them. Or embed C, but that's cheating, 'cuz it's no longer ruby

2013-03-13 22:12:29 Dr. Code
I think the time limit is not 6s or they are not testing n-m<=100000 and putting m=1 and n=1000000000 ..

2013-03-13 22:12:29 Diogo Soares [UFAM]
@darky1 yeah! Sieve is good enough..

2013-03-13 22:12:29 Darky
Is sieve of eratosthenes good enuf?

2013-03-13 22:12:29 Gaurav Singh
Hi,
After submitting the code i got RESULT as WRONG ANSWER; TIME 0.01 MEM 2760
How can i check where it went wrong?

Last edit: 2012-04-08 09:49:18

2013-03-13 22:12:29 nikhil kumar singh
wats the solution to get rid of time limit exceeding problem..??

2013-03-13 22:12:29 Vladimir Milenkovic
MY programe works fine, time limit is 6s, in worst test case it works for 4.84 s on ideone.com , and it's always Time limit Exceeded :( Why??

2013-03-13 22:12:29 Sardar Khan
how to solve sigsev error?

2013-03-13 22:12:29 sudarshan
i m new here.. i think the problem can be done by using sieve erosthanes .. starting with 2, we check every prime ,and separate the composite ones, for each test case, we can check in btw.. i know it sounds obvious, but could you help me, in finding the soln..