# Sieve of Eratosthenes

I want to spend a little moment to give some appreciation to Eratosthenes. This guy was pretty frickin’ awesome. Later in this post, I’ll explain how the Sieve of Eratosthenes allows you to find all prime numbers in a range. Other accomplishments under this guy’s belt:

• invented the discipline of geography
• invented chronology, the science of figuring out when things occurred in relation to each other in the past
• first person to calculate circumference of the Earth
• lived in the 200s BC for goodness sake!!
• figured out this sick method for finding prime numbers I’m about to show you

#### Finding Prime Numbers

Okay, so here’s the deal. Given a number, how do you calculate all numbers between 0 and that number which are prime?

To start with, we will want an array of all numbers, and we can just use a boolean at each index to specify whether or not it’s prime.

`function findPrimes(n) {  //create an array of true values  var nums = new Array(n).fill(true)}`

Maybe you could just go through all numbers, and then just see if each number is divisible by any earlier number. You might be tempted to write something like this:

`function findPrimes(n) {  var nums = new Array(n).fill(true)  for (var i = 2; i < n; i++) {    for (var j = i; j > 0; j--) {      ...`

I’m gonna stop you right there. This might seem easy, but this method will get pretty crazy crazy when the numbers start growing even a little bit. That kind of brute force solution will only get you so far.

Let’s not do that.

Let’s learn from the ancient wisdom of Eratosthenes.

#### The Sieve of Eratosthenes Algorithm

Here is how the Sieve of Eratosthenes works. You create a list of all numbers. For each number, you eliminate any later numbers in the list that are divisible by that number. Is this starting to sound like a program?

Here’s how you would write out this algorithm:

`function findPrimes(n) {  var nums = new Array(n).fill(true)    // loop through all numbers    for (var i = 2; i < n; i++) {      // if nums values is true, this number hasn't been reached yet      if (nums[i]) {        // for every number after this number        for (var j = i+1; j < n; j++) {          // if it is divisible by i, it cannot be prime          if (j % i === 0) nums[j] = false;        }      }    }    // only return numbers that have value of true    return nums.map(function(val, idx){       if (idx > 1 && val) return idx;    }).filter(function(val) { return val; });}`

That should do it!

#### Optimizing it…

But we’re doing some unnecessary work here. For one, if we know we only care about numbers divisible by i, we can just increment by i and ignore all other numbers, rewriting that section as such:

`// for every number divisible by this numberfor (var j = i * 2; j < n; j += i) {  nums[j] = false;}`

#### Optimizing it more…

We can do even better. You can actually start eliminating from the square of i, like so:

`// for every number after this number's square that's divisible by this numberfor (var j = i * i; j < n; j += i) {  nums[j] = false;}`

#### Optimizing it even more!

Would you like a fun fact? Here’s a fun fact. Did you know that, with this method, by the time we reach the square root of n, we will have found all the prime numbers? It’s true! So you can optimize even further to end up with a final version like so:

`function findPrimes(n) {  var nums = new Array(n).fill(true)  // loop through all numbers  for (var i = 2; i < Math.sqrt(n); i++) {    // if nums values is true, this number hasn't been reached yet     if (nums[i]) {      // for every number after this number      // for every number divisible by this number      for (var j = i * 2; j < n; j += i) {        nums[j] = false;      }    }  }   // only return numbers that have value of true   return nums.map(function(val, idx){    if (idx > 1 && val) return idx;  }).filter(function(val, idx) { return val; });}`

And there you have it! Using the above function you can find all primes (a lot faster than with the brute force approach).

What do you think? Do you see anything else that can be optimized? Feel free to comment or send me an email!

Originally published at paloobi.tumblr.com.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.