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)

Added by:	Adam Dzedzej
Date:	2004-05-01
Time limit:	6s
Source limit:	50000B
Languages:	All except: TECS

hide comments

2010-03-12 09:08:30 Muhamed Buvanov
(SIGSEGV) that error shows that array is too small for your operation

2010-03-08 08:51:56 wang yu
my program works fine on my own machine even under boundary conditions but got SIGSEGV here. that's strange

2010-03-01 22:36:51 Loukas Xanthos
TLE for me...I'm surprised because I've implemented a sieve of Eratosthenes in C++ and of course I store my primes and use any of them I want on the output part.... :P and it's TLE!

Last edit: 2010-03-01 22:38:42

2010-02-28 09:39:04 praveen
i am new to this place i got runtime error (SIGSEGV) plz any one help me

2010-02-26 20:56:53 Graham Poulter
In Java it takes 2.32 seconds. In C++ it takes 0.06 seconds. But in Python it times out... any ideas on doing better than a list of sieves in Python?

2010-01-31 06:41:21 karthik
i solved this problem by finding biggest bound(n)and store primes from 2 to ceil(sqrt(n)) in array (a[10000]) then i used this array to check number from input range prime or not.. it produced correct answer and also very quick . but when i upload it in spoj . it says wrong answer .. i dont know why..

2010-01-28 21:27:20 Kacper Wikieł
Chinese Primary test is too slow;
I think Eratosthenes sieve will go faster.

2010-01-04 22:10:58 Giovanni Botta
Can't figure this out: on my laptop (Intel Celeron 1.7 GHz, 2 GB RAM, WinXP Home) the worst case 999900000 1000000000 works fine, even if it's slow, and when I upload it on spoj i get a SIGABRT... Ideas?

2009-11-22 08:16:56 Arvind S Raj
I solved this problem using sieve's algorithm to find the primes in the given range. It works fine in my machine but generates a sigabrt() when i upload and run it in spoj. what is wrong?

2009-11-13 08:17:53 anonymous
abhirut, find the biggest bound (n), and save all the primes from 2 -> n somewhere

you can refer to that collection every time to check for primes.

there is no need to calculate all the primes every time

Last edit: 2009-11-13 08:18:27