The Sieve of Eratosthenes

Hey Firehoser’s(and anyone else who stumbled upon this), welcome to my blog and of course my very first blog post! I’ll start off with a little something about myself: I have been interested in computer programming since learning python when I was in 7th grade on a 10" dell notebook that could hardly run IE let alone visual studio. I’ve moved on to the beautiful language of c++, and while that is my preferred language, I’m actually getting along quite well with Ruby as I’m going through the Firehose Project.

Let’s get nerdy

I went along with the suggestion to “get nerdy” and write a prime number generator using The Sieve of Eratosthenes. The link in the Firehose challenge to a wikipedia article was enough for me to grasp the basic concept of what this algorithm needs to do. I implemented it in c++ after coming up with pseudocode on a whiteboard.

The Sieve of Eratosthenes is a method of identifying prime numbers in a given list of (2..n). It takes that list and starts with 2 (zero and one are purposefully not included this way), marking it prime, and then going through multiples of 2 up to the limit(n). It marks those as composite (not prime) values and continues to 3. Three is marked prime, and multiples of 3 are marked as composite up to the limit(n), then it continues with 4, and so on until you reach the square root of the limit(n), in our case it would be 10. Then it goes through all of the remaining numbers not marked composite, assumes they are prime and prints the results. It looks like this in code:

#include <iostream>
#include <cmath>
using namespace std;

int main(){
  const int SIZE = 101;                               //section 1
  int integers[SIZE];
  for (int i = 0; i < SIZE; i++){                     //section 2
    integers[i] = 0;
  }
  for (int i = 2; i < sqrt(SIZE); i++){              //section 3
    for (int p = 2, j = 0; (i*p) < SIZE; p++){
      j = i * p;  
      integers[j] = 1;
      }
  }
  for (int i = 2; i < SIZE; i++){                   //section 4
    if (integers[i] == 0){ 
      cout << i << ", "; 
    }
  }
  return 0;
}

So let me walk you through what’s going on:

Section 1:

This first step creates a const int called SIZE and initializes it to the value 101. If you’re not sure why 101, that’s because I want my array to be able to have an index of 100 since that’s what we’re supposed to go up to (if you’re still confused, google “off by one error”). The next line declares an integer array called integers[SIZE] and the size of this array is set to our SIZE variable. I chose 101 because I know exactly how many values to go up to, if you wanted to use a form of user input to set the array size or don’t know exactly how many elements you will have, I would suggest using a vector element instead.

Section 2:

This next step goes through each element in the array one-by-one, and sets each value to our default of zero. Instead of a bool array with values true and false, that would denote prime and composite respectively, it made more sense in my head to use an integer array with values; zero corresponding to prime numbers, and one corresponding to composite numbers. So, currently our program is assuming every number is prime, we’ll get to why that is later. For now, just know that everything is set equal to zero.

Section 3:

So in this section there are two iterative loops that work together to filter out the prime numbers from composite numbers. Looking at the first loop we see:

for (int i = 2; i < sqrt(SIZE); i++){ ... }            //section 3

this is saying that starting with an integer called i , and until i is less than the square root of the SIZE variable, it should do all of the code within the curly braces, increment the i variable and continue iterating until i is no longer less than sqrt(SIZE). Now, keep all of that in mind as we go to the next few lines of code:

...{ 
 for (int p = 2, j = 0; (i*p) < SIZE; p++){
    j = i * p;
    integers[j] = 1;
  }
}

this is saying that a variable p should be incremented from 2 until (i * p) is no longer less than SIZE, and while that happens a variable j is set to i * p, so what’s happening here?

Well, if you look back at the explanation of The Sieve of Eratosthenes, you’ll see that we need to store the value 1 into every array element that is a multiple of 2, 3, 4, 5, 6, 7, 8, 9, and 10. To do that we take each of those numbers, one at a time, and multiply it by every number until the product of i * p becomes greater than 101. Every time we multiply those values, the product gets stored into a variable j which is then used as the index for our array. Then, the element corresponding to that j value is filled with a value of 1 to denote it is a composite number and should not be displayed to the user.

Section 4:

This is the last part of the program that outputs the results to the user:

for (int i = 2; i < SIZE; i++){                   //section 4
if (integers[i] == 0){ 
      cout << i << ", "; 
    }}

So, our array has index values for 1 and 0 that are currently still initialized to 0 making them appear to our program as prime numbers that should be included in the output. However, we know that this isn’t true and we want to get rid of them. To do that you simply begin the loop with the iterator set to 2 forcing your program past integers[0] and integers[1] giving us the index number, variable i, from 2 to 100 where the values inside that element is 0.

Thanks for reading! I hope you enjoyed this as much as I did!