The Sieve of Eratosthenes

Generating a multiplication table with the first N prime numbers.

Introduction

This post is for walking you through the steps I have taken for creating a command line tool for printing out a multiplication table of the first N prime numbers. The result is a gem called primes_table and for the related code, you can take a look to this repository.

Stack:

• Methadone an awesome project for creating command-line tools;
• Ruby version 2.5.0;
• RSpec as a testing framework;
• Simplecov for code coverage;
• CodeClimate for engineering process insights and automated code review;
• SemaphoreCI for continuous integration;

Input

The command line tool will receive two parameters rows and columns.

Specifications:

• By default the table will be generated as a matrix of 10X10;
• Only values greater or equal than 10 will be considered for specifying rows or columns;
• If you enter a value minor than 10, it will default to 10;
• Only integer values are considered. For example, if you enter a string, it will be converted to an integer, the result will be 0 (zero) and will default to 10 because zero is minor than 10;

Output

A multiplication table with the first N prime numbers. The first row and column are the respective prime numbers.

For example, the default output will have as the first column, the first prime numbers until number 10. This means numbers 2, 3, 5 and 7. The same with the first row. The following image should help you visualize the desired output:

Creating the gem

With methadone installed you just need to run:

methadone --readme --rspec --license apache primes\_table

That command will generate the skeleton of your command line tool.

I have created an extra couple of options to add to the ones already included when you create the project. After that, all the options are:

• -h, --help to see the available options;
• -r, --rows ROWS to specify how many rows;
• -c, --columns COLUMNS to specify how many columns;
• --version it will give you the version of the gem you are using;

The following code handles the case where no options are entered. The default option is always going to be 10 for rows and columns.

	#!/usr/bin/env ruby
	require 'optparse'
	require 'methadone'
	require 'primes_table.rb'
	class App
	include Methadone::Main
	include Methadone::CLILogging
	main do
	rows = options[:rows].to_i < 10 ? 10 : options[:rows].to_i
	columns = options[:columns].to_i < 10 ? 10 : options[:columns].to_i
	args = { rows: rows, columns: columns }
	matrix = Matrix.new(args)
	matrix.print
	end
	description 'Prints out a multiplication table of the first N prime numbers.'
	on('-r ROWS', '--rows', 'Amount of rows in table. Must be integer. Default value is 10.')
	on('-c COLUMNS', '--columns', 'Amount of columns in the table. Must be integer. Default value is 10.')
	version PrimesTable::VERSION
	go!
	end

view raw primes_table hosted with ❤ by GitHub

Naive approach

The first approach was to loop over each number from 2 to N. This means that per each number I was iterating over it in order to check whether there was not another divisor than himself.

	class Prime
	class << self
	def prime?(number)
	return false if number < 2
	(2...number).each do |i|
	return false if (number % i).zero?
	end
	true
	end
	def generate_primes(limit)
	collection = []
	(1..limit).each do |number|
	collection << number if prime?(number)
	end
	collection
	end
	end
	end

view raw prime.rb hosted with ❤ by GitHub

On the other hand, we have the Matrix class with a private method called header that returns the list of primes numbers I want, until the given N.

	class Matrix
	attr_accessor :rows_header, :columns_header, :table
	def initialize(args)
	rows = header(args[:rows])
	columns = header(args[:columns])
	@table = load_table(rows, columns)
	@rows_header = rows
	@columns_header = columns
	end
	def print
	distance = last_value.to_s.length
	puts format_columns_header(distance)
	table.each_with_index do |row, index|
	puts format_rows(row, index, distance)
	end
	end
	private
	def header(limit)
	Prime.generate_primes(limit)
	end
	def load_table(rows, columns)
	collection = []
	rows.each_with_index do |row_value, row_index|
	collection << []
	columns.each do |column|
	collection[row_index] << row_value * column
	end
	end
	collection
	end
	def last_value
	table[-1][-1]
	end
	def format_columns_header(distance)
	"#{' ' * distance} #{format_collection(columns_header, distance)}"
	end
	def format_rows(row, index, distance)
	len_index = rows_header[index].to_s.length
	format_prime = "#{rows_header[index]}#{' ' * (distance - len_index)}"
	collection = format_collection(row, distance)
	"#{format_prime} | #{collection}"
	end
	def format_collection(list, distance)
	list.collect { |i| ' ' * (distance - i.to_s.size) + i.to_s }.join(' ').to_s
	end
	end

view raw matrix.rb hosted with ❤ by GitHub

Making improvements

Once I got that working, I thought that it has to be a better approach to solving it. I'm iterating from 2 to N and over that list of numbers, I'm iterating again form 2 to N[i] checking for primality. So I checked in one of the books I have entitled Cracking the Coding Interview and there it was. Two improvements that can be done.

The first improvement was to iterate not from 2 to N[i] but to the square root of this number. So the code will look something like this:

	class Prime
	class << self
	def prime?(number)
	return false if number < 2
	sqrt = Math.sqrt(number).to_i
	(2..sqrt).each do |i|
	return false if (number % i).zero?
	end
	true
	end
	def generate_primes(limit)
	collection = []
	(1..limit).each do |number|
	collection << number if prime?(number)
	end
	collection
	end
	end
	end

view raw prime.rb hosted with ❤ by GitHub

The sqrt(n) is sufficient because for every number a which divides n evenly, there is a complement b , where a * b = n . If a > sqrt(n) , then b < sqrt(n) (since (sqrt(n))**2 = n). We, therefore, don't need to check n 's primality, since we would have already checked with b .

The next improvement is to implement The Sieve of Eratosthenes. This is a highly efficient way to generate a list of primes. It works by recognizing all non-prime numbers are divisible by a prime number.

We start with a list of all numbers up through some maximum value. First, we cross off all numbers divisible by 2. Then, look for the next prime (the next non-crossed off number) and cross off all numbers divisible by it. By crossing off all numbers divisible by 2, 3, 5, 7, 11, and so on, we wind up with a list of prime numbers from 2 through a maximum.

	def header(max)
	flags = [true] * (max + 1)
	flags[0] = flags[1] = false
	prime = 2
	while prime <= Math.sqrt(max)
	cross_off(flags, prime)
	prime = next_prime(flags, prime)
	end
	process_flags(flags)
	end
	def cross_off(flags, prime)
	(prime * prime..flags.length).step(prime).each do |i|
	flags[i] = false
	end
	end
	def next_prime(flags, prime)
	following = prime + 1
	following += 1 while following < flags.length && !flags[following]
	following
	end

view raw sieve_of_eratosthenes.rb hosted with ❤ by GitHub

As you can see the method header calls process\_flags at the end. This is not part of The Sieve of Eratosthenes calculations since we are using it only to get the primes numbers based on the flags we have:

	def process_flags(flags)
	primes = []
	flags.each_with_index do |value, index|
	primes << index if value
	end
	primes
	end

view raw process_flags.rb hosted with ❤ by GitHub

At the end our class Matrix will look something like this:

	class Matrix
	attr_accessor :rows_header, :columns_header, :table
	def initialize(args)
	rows = header(args[:rows])
	columns = header(args[:columns])
	@table = load_table(rows, columns)
	@rows_header = rows
	@columns_header = columns
	end
	def print
	distance = last_value.to_s.length
	puts format_columns_header(distance)
	table.each_with_index do |row, index|
	puts format_rows(row, index, distance)
	end
	end
	private
	def load_table(rows, columns)
	collection = []
	rows.each_with_index do |row_value, row_index|
	collection << []
	columns.each do |column|
	collection[row_index] << row_value * column
	end
	end
	collection
	end
	def last_value
	table[-1][-1]
	end
	def format_columns_header(distance)
	"#{' ' * distance} #{format_collection(columns_header, distance)}"
	end
	def format_rows(row, index, distance)
	len_index = rows_header[index].to_s.length
	format_prime = "#{rows_header[index]}#{' ' * (distance - len_index)}"
	collection = format_collection(row, distance)
	"#{format_prime} | #{collection}"
	end
	def format_collection(list, distance)
	list.collect { |i| ' ' * (distance - i.to_s.size) + i.to_s }.join(' ').to_s
	end
	def header(max)
	flags = [true] * (max + 1)
	flags[0] = flags[1] = false
	prime = 2
	while prime <= Math.sqrt(max)
	cross_off(flags, prime)
	prime = next_prime(flags, prime)
	end
	process_flags(flags)
	end
	def cross_off(flags, prime)
	(prime * prime..flags.length).step(prime).each do |i|
	flags[i] = false
	end
	end
	def next_prime(flags, prime)
	following = prime + 1
	following += 1 while following < flags.length && !flags[following]
	following
	end
	def process_flags(flags)
	primes = []
	flags.each_with_index do |value, index|
	primes << index if value
	end
	primes
	end
	end

view raw matrix.rb hosted with ❤ by GitHub

A couple of things to notice here is that I'm not using the class Prime anymore. I have taken this decision because the actions I want to perform are related to the Matrix itself and at the moment I don't really see the need for spreading the logic into another class. In the future, if the project grows in some way, I could evaluate how to scale it. But at the moment, I don't have enough information to do it.

Notes

As I mentioned at the beginning of this post, all code is Open Source and it can be found in this repository.

If you think that I should have taken a different approach or maybe you have a couple of ideas that you would like to implement, don’t doubt it and make a PR right away ☺.

One thing to notice is that right now I’m calculating the list of prime numbers for both, rows and columns. I think this could be improved. If rows are equal to columns it should be enough with calculating the list of primes only once.

Another improvement could be to only calculate the list of primes of the biggest number that was entered as row or column. In the process of calculating the list of prime numbers for the biggest number entered, we should be able to collect the prime numbers for the minor value as well.

---