A Programmer’s Quest for Primes: Part 2 – Sieve of Eratosthenes

6 03 2009

This is part 2 of my quest to calculate prime numbers using small and efficient programs written in C. In the first part I wrote a program to brute force find primes by testing sequential numbers to see if they were divisible by any other prime numbers found before, and making the process a bit faster by only checking odd numbers and stopping when I reach a prime greater than the square root of the number in question.

For my second prime calculating program I make use of an algorithm developed 2,200 years ago by the Greek mathematician Eratosthenes. A friend once told me all the great computer science ideas were developed 20 years ago. I often tend to think it was further back than that. Division and modulus commands are very costly in terms of CPU cycles. Multiplication and addition are much faster. Rather than checking to see if a number is prime by dividing it by all prime numbers found before it, it’s much faster to multiply the prime numbers to find all the composites, and then mark anything remaining as prime.

animation_sieve_of_eratosth-2

A bit array would be the ideal data structure for this algorithm, but because C doesn’t have a bit array structure built in. The only other option is use the bool datatype (C99) or an unsigned char (ANSI), but either way you’re wasting 7 bits of memory for each element (you only need one bit). While searching for bit arrays in C I found another programmer’s quest for calculating prime numbers here, http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm.

Rather than reinventing the wheel I just finished up my much simpler version using char arrays to find the first 100 million primes. The code can be found here, http://pherricoxide.jumbofx.com/code/eratosthenesprimecalc.c. After this point it starts running out of RAM though, so to find more primes you’ll have to use a paging or cluster method as coded in the last link.

Using the brute force program it took over 2 hours to compute the first 100 million primes.

Using this method, it took less than 7 minutes. Quite a difference to say the least. The only downside is that this algorithm uses much more RAM.

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: