Thursday, April 14, 2011

Primes and the Sieve of Eratosthenes

My nephew was working on finding how many primes are below a certain upper bound, so I was playing with this some today as well. Initially, since he was working in perl I threw together a quick perl program that built a list of primes below a certain upper bound. I also wrote a routine to determine the prime factorization of a number. The perl program would get bogged down after a while though between the algorithm implementation and just the speed of perl.

To speed things up I moved to c++ and implemented the same algorithm, and played around with using vectors to store the list of primes. That sped it up some, but it would still eventually get bogged down by the algorithm.

So finally I decided to implement the Sieve of Eratosthenes using a bit array. Now that got things going quickly. It is a fast algorithm that is pretty much bound by the amount of memory you have. On my home system it did the following for an upper bound of 1 billion:

snits@perelman:~/proj/cpp=>time ./se 1000000000
50847534 primes between 2 and 1000000000. Greatest prime is 999999937

real 1m58.563s
user 1m58.352s
sys 0m0.101s

I bumped the upper bound up to 40 billion, which would take a fair chunk of my RAM for the bit array, and it had the following results:

snits@perelman:~/proj/cpp=>time ./se 40000000000
1711955433 primes between 2 and 40000000000. Greatest prime is 39999999979

real 90m48.631s
user 90m40.850s
sys 0m3.589s

No comments:

Post a Comment