OJ Board

Using Seive method it is possible to generate all primes between n=sqrt(2^31-1).
But if we need the next all prime upto 2^31-1. Then what should we do?

Plz someone clarify this algorithm with example.

Thanks
Sumon

there are far too many primes to generate in the range from [2, 2^31). even if there were a method to generate these primes directly in O(1) one after the other (which by the way is not the case), storing them all would be an issue.

i suggest looking at http://primes.utm.edu/howmany.shtml to get an idea of how many primes there really are.

http://www.spoj.pl/problems/PRIME1/

this is an example of a problem that seems to ask you to calculate all primes till 2^31, but that is not the case. usually primes that need to be found in a small range (smaller then 1Million maybe) can be done so using a slight modification to the standard sieve.

the idea is, sieve numbers from [2, sqrt(2^31)] (small range, smaller sieving time)
then for each of these numbers, sieve numbers in the range that is asked.

a few more ideas (though i never used them in programming contest myself) is more sophisticated primality tests, such as pseudo-prime test, rho test. googling for them will tell you about such tests.