code 3:20, LLC

Website Design, Hosting, Re-Design and Development

  • Home
  • Design
  • Solutions
  • Sites
  • Contact
  • Geeks

Oct 22 2015

Sieve of Eratosthenes

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:

Screen Shot 2015-10-22 at 1.30.40 PM

Safe coding, my friends!

Written by Randy · Categorized: Web Development

Oct 18 2015

Code Editor of Choice

Atom.io screenshot

Recently (October 5), I started the Firehose Coding Bootcamp.  It feels like truly drinking from a firehose!  I’ve learned so many things that I didn’t know such as using Github for version control, web app deployment on Heroku, cloud file storage and integration, installation and configuration of Ruby Gems, Postgresql DB setup and use, etc, etc, etc.  Drinking from the firehose…

After using many, I’ve also found my favorite editor called Atom.  From their website:

Atom is a desktop application built with HTML, JavaScript, CSS, and Node.js integration. It runs on Electron, a framework for building cross platform apps using web technologies.

It is so very extensible it is crazy.  I installed it and added these packages that are saving me SO much time: git-plus and rails-snippets.

With the git-plus package, you can pretty much do anything you have to do with your terminal from within the editor.  I “git add –all”, “git commit -m “message”” (with a message edit that pops up and shows me everything that has changed and is on the stage) and “git push origin master” all with Cmd-Shift-A p.  That alone is worth the price… FREE!  One “gotcha” when developing with a virtual machine is that to use git-plus, I had to setup separate SSH key access to my Github account in addition to the key I use within my Web Dev environment.  I followed this tutorial: https://help.github.com/articles/generating-ssh-keys/ from the good folks at Github.  Finally, you have to launch Atom from the CLI for everything to work within Atom.  In all fairness, I didn’t investigate too long how to launch Atom within my Web Dev environment.  As of this writing, I haven’t setup my Heroku keys so that I can push from within the editor.  I still use the terminal for Heroku interaction.  Atom doesn’t recognize the Heroku keys I setup through Vagrant and I just haven’t had time to investigate it on this end of the firehose.

The rails-snippets save a lot of time.  For example, <%=   %> can be inserted with Cmd-Shift->.  It auto fills do loops and so much more.  What a time saver.  And did I mention totally customizable?

Finally, Atom does everything you’d expect in a great code editor such as autofill HTML, CSS, Ruby, etc…  And, did I mention it is customizable???

Written by Randy · Categorized: Mac Tips, Software Tools, Web Development

May 30 2015

Anytime Locksmith

AnytimeLocksmithAnytime Locksmith is located in Jackson, Mississippi.  code 3:20 was contracted to re-design the site.  We created a responsive website built WordPress using the Genesis Framework with the Attitude Pro child theme.  code 3:20 designed the logos for the site and customized the CSS to present a website that will set Anytime Locksmith above and beyond the competition!

Check it here>>  Anytime Locksmith

Written by Randy · Categorized: Redesign, Web Development

Jan 29 2015

MAMP and Yosemite

MAMP_Logo

I updated to the latest version of MAMP after recently updating my Macbook Pro OS to Yosemite so that I could develop websites within my local environment, then deploy to my web servers. Much to my chagrin, after the update, the MySQL database server within MAMP would not start.  Here are the steps I took to make it work within Yosemite:

  1. If MAMP  is running, quit the application.
  2. Find the file named envars_ and rename to _envars.  The path to the file is: Applications/MAMP/Library/bin/
  3. Open Activity Monitor and search for the mysqld process.  If it is running, kill it.
  4. Start MAMP and the MySQL server will run.

Good luck and good coding…

Written by Randy · Categorized: Web Development

Jan 08 2015

Remote Assistance

teamviewer

code 3:20, LLC has purchased a license for TeamViewer version 10. We use this software to collaborate with our clients via the meeting aspect of TeamViewer when designing software or a new website. We also use it to take remote control of customer computers (obviously under the complete purview of the customer) to assist with computer issues such as virus/worm/trojan elimination; configuration of computers, printers, networks, etc; elimination of unnecessary computer processes that slows execution of the computer; and any other customer computer need.

Written by Randy · Categorized: Redesign, Web Development

  • 1
  • 2
  • 3
  • Next Page »

code 3:20 Posts

April 2021
S M T W T F S
 123
45678910
11121314151617
18192021222324
252627282930  
« Nov    

What’s New

  • Site Morph to Responsive
  • Sieve of Eratosthenes
  • Code Editor of Choice
  • Time Differences for My Friends
  • Old Pascagoula Mini Storage

Archives

© 2012–2021 - code 3:20, LLC · All Rights Reserved ·