Eratosthenes Meets Ruby

The Sieve of Eratosthenes is an ancient algorithm used to find prime numbers up to a maximum number. As you might have guessed, it is attributed to the Greek mathematician Eratosthenes.

The man himself!

I recently coded a Ruby method to simulate how it works. In this inaugural blog post, I break it down by comparing my method to an example on Wikipedia

Step 1. Create an Array of Integers

Let’s say we want to find all prime numbers less than or equal to 30.

If I was Eratosthenes, my first step would be to write all integers between 2 and 30 on a good old piece of papyrus:

In Ruby, consider —

def primes(max_number)
  integers = []
i = 2
end 

First we define a method called primes that will take a max_number argument and output the prime numbers up to that max_number.

Within the method, we create a blank array called integers & set the first integer equal to 2.

def primes(max_number)
  integers = []
i = 2
  while i <= max_number
integers << i
i = i + 1
end
  p integers 
end
primes(30) # Our Test Case

We use a while loop that repeats the following code over and over again: it adds the integer i to the integers array (integers << i) & then adds the next integer (i = i + 1). It continues to add integers while the integer i is <= max_number.

The last line in the method, p integers — outputs the integers array so far. When we run the ruby code above we get this:

Just like Eratosthenes’ first step!

Step 2. Cross off the First Prime Numbers’ Multiples

Eratosthenes would then cross off the multiples of the first prime number on the list, 2.

(So… 4, 6, 8, 10, etc.)

Another while loop can accomplish this in Ruby —

def primes(max_number)
  integers = []
i = 2
  while i <= max_number
integers << i
i = i + 1
end
  index = 0 
multiplier = 2
  while (integers[index] * multiplier) <= max_number
integers.delete(integers[index] * multiplier)
multiplier = multiplier + 1
end
  p integers
end
primes(30) # Our Test Case

We set the index of the first prime number we are looking at in the integers array. The first number, 2, has an index of 0.

The expression (integers[index] * multiplier) is a multiple of integers[index]. We do not count integers[index] as a multiple so we always set the multiplier equal to 2.

The while loop runs the following code until the multiple is <= max_number. It will delete the multiple from the array — then increase the multiplier by 1, to move onto the next multiple.

Running the code outputs the following —

Step 3. Cross off the Rest of the Prime Numbers’ Multiples

Eratosthenes would then move to the next prime number that hadn’t been crossed off, 3… 
then cross off its multiples — 
(6, 9, 12, etc.)

Then the next prime number that hadn’t been crossed off, 5… 
then cross off its multiples — 
(10, 15, 20, etc.)

He would repeat this pattern until he was left with all the prime numbers from 2 to 30

def primes(max_number)
  integers = []
i = 2
  while i <= max_number
integers << i
i = i + 1
end
  index = 0 
multiplier = 2
  while integers[index] != nil
while (integers[index] * multiplier) <= max_number
integers.delete(integers[index] * multiplier)
multiplier = multiplier + 1
end
    index = index + 1
multiplier = 2
end
  p integers
end
primes(30) # Our Test Case

By putting the while loop in Step 2 within another while loop, we can access the next number of the integers array with index = index + 1. We also need to remember to reset the multiplier to 2.

Once we have our next number, we can run the previous loop to find its multiples —

while (integers[index] * multiplier) <= max_number
integers.delete(integers[index] * multiplier)
multiplier = multiplier + 1
end

index = index + 1 will exceed the integers available in our array when it reaches an index outside the array’s limits and returns something that doesn’t exist, so we should run the new loop while integers[index] != nil.

With this new loop we can find the multiples of each prime number after 2 and get rid of them to output — .

And just for fun we can test the method with primes(100) & yield even more primes —

Closing Thoughts

I imagine I could have picked a more exciting topic for my first blog post, but I appreciate the exercise of blogging about code as something entirely different from just doing the code.

As a student full-stack web developer for The Firehose Project, teaching what you know really feels like the best way to learn.

I’ll blog about myself and my coding journey soon. Until next time!