Sieve of Eratosthenes

I have seen a LOT of algorithms since diving into Computer Science, but the Sieve of Eratosthenes model for generating prime numbers has so far been my favorite. I think most of us have been in a situation where learning a new algorithm that only slightly boosts amortized run time or space complexity while adding a hundred lines of code, but for me, the Sieve of Eratosthenes was such a mind boggling improvement I had to write about it. There are likely hundreds of ways to generate prime numbers, and check if a number is prime. One of the first programs I ever wrote was a JavaScript program that checked if a number was prime by iterating through all the numbers less than the input value, and checking if all numbers below THAT were divisible by the earlier iterative. Not such a program. At least I can admit it happened, right?

The Sieve of Eratosthenes works by generating a list of boolean values for each number less than our input, and setting them all to true. We then start at 2, and since it is marked as true, we know it is prime. We then mark off all numbers in our boolean set that are divisible by two as False, since any number divisible by a prime is obviously not prime. We then move to 3, and since it is marked as True, we know it is prime. We then mark off all multiples of 3, and repeat this process. We terminate the program when the square of a prime number is greater than our input value, and return our list of prime numbers. If we want a list of integers returned instead of an array of boolean values, we could just iterate through our list, appending the index of each cell still marked as true.

My code on GitHub can be found here if you want to check it out:

https://github.com/n8sters/Sieve-of-Eratosthenes/blob/master/SieveOfEratosthenes.java

While it may not be the most interesting, the simplicity and efficiency of this algorithm compared to the naive approach makes it worth mentioning. Additionally, it dates back to roughly 276 B.C., which is just cool.

Thanks for reading!

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s