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!


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.


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.


1 10
3 5


Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)


After cluster change, please consider PRINT as a more challenging problem.

hide comments
joseph guichebarou: 2013-03-13 22:12:29

quick question... I am trying to do this problem in python. The high level description of my algorithm is for each number in the given range of the test case, to loop from 2 to sqrt of the current number looking for a factor. if a factor is not found then i know that the number is prime. i cache that number and if it is the first test case i print it. on subsequent test cases i check the cache to see if i've already computed the primes in the range of the current test case. the problem i am having is that i am getting a "time limit exceeded" error. i was certain that this algorithm was more efficient than i sieve. any suggestions? p.s. i also immediately skip over any even numbers

Last edit: 2011-08-28 20:04:38
joseph guichebarou: 2013-03-13 22:12:29

@hazem - i'm assuming you're using an array for your sieve. when you say "new" that assigns things to the heap. either change the size of your array or change the amount of memory that is allocated to the heap at start up. you can do this via command line, or if you are using an IDE then there is probably a way in the settings to change that

Michael T: 2013-03-13 22:12:29

@pfiesteria: Either change your algorithm or use psyco then.

@Giovanni: Two words - segmented sieving. It is simple, really, easily writable by oneself.

pfiesteria: 2013-03-13 22:12:29

I got A.C. in C++ code within 1 second by sieve, but got TLE with python 2.5 code and same algorithm. I wonder why python can got A.C ? Is there a fast I/O in python?

Last edit: 2011-09-17 10:50:23
Giovanni Botta: 2013-03-13 22:12:29

@Eclipse: I had seen that already. The algorithm is not fast enough though: 17 seconds to generate all primes up to 10^9 on my machine...
I found this one
which is incredibly fast (about 3 sec), but the code is almost unreadable. I'm working on writing a code using the guidelines described there but better commented!

Giovanni Botta: 2013-03-13 22:12:29

@Hazem: if you are using too much memory it means you are probably not using bit sets but an actual list of integers...

Hazem: 2013-03-13 22:12:29

please help me when i solve by sieve
give me java.lang.OutOfMemoryError: Java heap space

Vimeet Gautam: 2013-03-13 22:12:29

Thnx Sir for your help @Michael T

Michael T: 2013-03-13 22:12:29

@Alexey: So hard to check? Read input and do nothing - you should get WA.

Alexey: 2013-03-13 22:12:29

Are you sure you have exactly t lines after integer t?
Having runtime, input reading is the ony vulnarable place

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