Big prime

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

Big prime

Post by rhsumon » 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.

Thanks
Sumon

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

Re: Big prime

Post by skinnyguy » 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.

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.

Post Reply

Return to “Algorithms”