Page 1 of 1
Posted: Wed Aug 20, 2008 4:18 pm
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
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.
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.