# 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.

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

**argument and output the prime numbers up to that**

*max_number***.**

*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 (

**& then adds the next integer**

*integers << i)**(*

**. It continues to add integers while the integer**

*i = i + 1)*

*i**is*

**.**

*<= max_numbe*rThe 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

**. We do not count**

*integers[index]***as a multiple so we always set the multiplier equal to 2.**

*integers[index]*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] != nilwhile (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

**. We also need to remember to reset the multiplier to 2.**

*index = index + 1*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!