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:
- Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
- Initially, let p equal 2, the first prime number.
- 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).
- 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!