Good ole Eratosthenes of Cyrene, a Greek mathematician, came up with an algorithm to find all prime numbers up to a limit. Since I’m a Ruby newbie, I decided to implement his algorithm and walk you through my process within the code. As time goes by and I leave the noob status behind, I plan on revisiting this code to re-factor it with eloquence, but for now, here we go…

Here is the algorithm from the wiki cite below:

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, … ; the p itself should not be marked).
4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

As background, you can read about the algorithm here at the wiki: Sieve of Eratosthenes

I defined a class called the “EratosthenesAlgo” and did the initialization as follows:

class EratosthenesAlgo
  def initialize
    print "\nEnter an integer greater than one: "
    @num = gets.chomp.to_i
    @eratosthenes = [*2..@num]
  end

I asked the user for an integer (didn’t do any input validation, as you can see) and stored the result within an instance variable designated “@num”. Since input from the keyboard is received as a string, I converted to an integer with the “to_i” built-in method. Finally within the initialization of the class, I created the initial list of numbers as an array using splat and starting with the first prime, 2 and assigned it to an instance variable designated “@eratosthenes”. These two variables are now available for use within the other methods within the class.

I created 2 methods within the class to handle the heavy lifting for the algorithm. The first is the iterator as defined:

def iterator
    i = 0
    primes = []
    while i < (@num**0.5).floor do
      @val = @eratosthenes.slice!(0)
      primes << @val
      if (@val**2) > @num
        break
      end
      deleteNonPrimesFromErato(@val)
      i += 1
    end
    finalArray = (primes << @eratosthenes).flatten
    puts "\n\n Prime numbers <= #{@num} are: \n\n #{finalArray.join(" - ")} \n\n"
  end

I started out initializing a counter local variable "i" and an array called "primes". The while loop checks the square root of the number entered at the beginning of the class initializer and makes sure that the number is an integer by using the "floor" method. For example, when the user enters the number 30 the square root is 5.477225575051661 then the "floor" method takes it to the integer 5. The while loop will be broken when @val**2 gets greater than the number the user entered because of the conditional; therefore, assigning the square root to the conditional for the while loop is artificially high. So, in our example of 30 as the user supplied number, the iterator will only run 4 times before the break condition is met (i.e., val**2 will equal 49 which is greater than 30). In the case of 100, it will run 5 times before the break condition is met (i.e., val**2 will equal 121 which is greater than 100). The "@val" instance variable holds the first value in the @eratosthenes array and the "slice!" method mutates the original array to pull the first element of the array out. I then push @val into the prime array as its first value, then call the "deleteNonPrimesFromErato" passing @val as a parameter. When it returns we increment the counter and repeat. Let's look at the final method of the class, then we'll come back (or return, pun intended).

The 2nd method of the class is defined here:

  def deleteNonPrimesFromErato(init_val)
    i = 0
    val = init_val**2
    cond = @eratosthenes.length
    while  i < cond do
      @eratosthenes.delete val
      i += 1
      val = (init_val**2) + (i*init_val)
      if val > @num
        break
      end
    end
  end

This method receives @val as its "init_val" argument, which is the prime that was "sliced" out from the iterator method. I initialize a local counter "i" and square the first prime and store it into the local (local to the method) variable "val". I initialize a loop and check against the length of the @eratosthenes array which was assigned to "cond", which is also an arbitrarily higher number than is necessary. For example, when the user supplied number is 30, the length of the array translates to 28 the first time the method is called and the break condition is met after only 14 loop iterations. The 2nd time the method is called, cond = 13 and the break condition is met after 8 iterations, etc. The body of the while loop deletes the number represented by "val" from the array. It's a pretty neat method to use since we don't have any repeating elements. Then the counter is incremented and "val" is incremented by its initial value squared plus the value of the iterator times the initial value. This comes from the formula for incrementing the multiples of the "init_val" in order to delete them out of our array. The while loop will continue deleting values from the array until "val" becomes greater than the user supplied number, then it will break out of the method and return control to the iterator.

Let's go back now and finish up the iterator:

def iterator
    i = 0
    primes = []
    while i < (@num**0.5).floor do
      @val = @eratosthenes.slice!(0)
      primes << @val
      if (@val**2) > @num
        break
      end
      deleteNonPrimesFromErato(@val)
      i += 1
    end
    finalArray = (primes << @eratosthenes).flatten
    puts "\n\n Prime numbers <= #{@num} are: \n\n #{finalArray.join(" - ")} \n\n"
  end

Once control is passed back, the counter "i" is incremented, the next prime in the @eratosthenes array is sliced out of the array and stored in @val. @val is also pushed into the "primes" array, the break condition is checked to see if this prime value squared is greater than the user supplied number, then, if it doesn't break, the "deleteNonPrimesFromErato" is called again with @val to be used as its "init_val". After all the iterations are done, the final array ("finalArray") is assigned by adding all of the remaining prime values still left within the @eratosthenes array. Then we "puts" the output to the terminal.

Of course, all this action doesn't occur without these lines:

eratothenes = EratosthenesAlgo.new
eratothenes.iterator

We first instantiate a new object from the EratosthenesAlgo class called, surprisingly: "eratothenes", then we use that variable to invoke the iterator method and the wonderful Ruby magic occurs...

Here is all of the code:

class EratosthenesAlgo
  def initialize
    # Get the number from the user and
    # convert the string input to an integer
    print "\nEnter an integer greater than one: "
    @num = gets.chomp.to_i
    # Create the initial Eratosthenes array from num using splat
    # and starting with the first prime number
    @eratosthenes = [*2..@num]
  end
  
  
  def iterator
    # Initialize a counter
    i = 0
    # Holder for initial primes
    primes = []
    # Loop to call the delete non primes
    while i < (@num**0.5).floor do
      # Pull the first prime from the array
      @val = @eratosthenes.slice!(0)
      # Push the value into our primes holder array
      primes << @val
      # Check to see if the prime value squared is > user-suppled number
      if (@val**2) > @num
        break
      end
      # Call the mutator method to delete non primes from the array
      deleteNonPrimesFromErato(@val)
      i += 1
    end
    # Combine what's left from original array to primes array
    finalArray = (primes << @eratosthenes).flatten
    # Print the final output
    puts "\n\n Prime numbers <= #{@num} are: \n\n #{finalArray.join(" - ")} \n\n"
  end
  
  # Iterator method for removing Non-Prime Numbers from the Eratosthenes array
  def deleteNonPrimesFromErato(init_val)
    # Init the loop counter
    i = 0
    
    # Square the value of the prime that was passed
    val = init_val**2
    # Set loop conditional artificially high
    cond = @eratosthenes.length
    while  i < cond do
      # Remove the multiples
      @eratosthenes.delete val
      # Increment counter
      i += 1
      # Get the next multiple
      val = (init_val**2) + (i*init_val)
      # If next multiple is greater than user supplied number, break
      if val > @num
        break
      end
    end
  end
end



eratothenes = EratosthenesAlgo.new
eratothenes.iterator

Here is the output for the integer 100:

Safe coding, my friends!