Page 1 of 1

Big prime

Posted: Wed Aug 20, 2008 4:18 pm
by rhsumon
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.


Re: Big prime

Posted: Thu Aug 21, 2008 5:53 am
by skinnyguy
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 to get an idea of how many primes there really are.

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.