Prime Products

Prime Products is a command-line tool which outputs the multiplication table of the first n prime numbers.

So, for instance, where n=5, you'd get a result like this:

+----+----+----+----+----+-----+
| *  | 2  | 3  | 5  | 7  | 11  |
| 2  | 4  | 6  | 10 | 14 | 22  |
| 3  | 6  | 9  | 15 | 21 | 33  |
| 5  | 10 | 15 | 25 | 35 | 55  |
| 7  | 14 | 21 | 35 | 49 | 77  |
| 11 | 22 | 33 | 55 | 77 | 121 |
+----+----+----+----+----+-----+

The first row and column of the table contains the first 5 primes. Each other cell contains the product of the primes for the corresponding row and column.

Installation

Install the gem by running gem install prime_products.

In development, you can install this gem by cloning the repository and running bundle.

Usage

To generate a table of prime products, run the prime_products executable, providing the size of the table as the first argument:

# If you have installed this gem from source, you will need to run
# `bundle exec prime_products 10`.
prime_products 10

If you do not provide an argument, we will use the first 5 by default.

Exploring the code

The code is logically separated into parts, in line with the single responsibility principle.

When you run the prime_products executable included with the gem, exe/prime_products is executed, which calls PrimeProducts::CLI.call.

PrimeProducts::CLI.call defaults to outputting the STDOUT and reading input from ARGV, but this can be customised, allowing for a "dependency injection" approach to testing.

It finds the number of primes to use, looking at ARGV and defaulting to CLI::DEFAULT_NUMBER_OF_PRIMES if no option has been provided.

It then calls PrimeProducts.generate_table with the number_of_primes, and writes the result to the output,

PrimeProducts.generate_table finds the requested number of prime numbers using PrimeProducts::PrimeNumbers::SieveOfEratosthenes.first, and then asks PrimeProducts::MultiplicationTable.generate to generate a multiplication table from them.

PrimeProducts::PrimeNumbers::SieveOfEratosthenes.first uses the performant Sieve of Eratosthenes method for finding primes - see the "Benchmarking" section below - and returns them in an Immutable::SortedSet to avoid the danger of accidental mutation.

Benchmarking

This gem uses the performant Sieve of Eratosthenes method of finding prime numbers (PrimeProducts::PrimeNumbers::SieveOfEratosthenes):

  • finding the first 10 takes ~0.0001s
  • finding the first 100 takes ~0.0006s
  • finding the first 1000 takes ~0.007s
  • finding the first 10000 takes ~0.1s

As is evident, it scales well for large numbers of primes.

The gem also includes, but doesn't use, a naive method of generating primes (PrimeProducts::PrimeNumbers::Naive). It is much less performant - but this trade-off here might be worth making for simpler code, given that for the use case of displaying multiplication tables, you would only ever want to generate a relatively small set of prime numbers:

  • finding the first 10 takes ~0.0001s
  • finding the first 100 takes ~0.003s
  • finding the first 1000 takes ~0.35s
  • finding the first 10000 takes ~44s

You can see full benchmark results, comparing the Ruby standard library's implementation (Prime.first) to these implementations, by running ruby benchmarks/prime_numbers.rb.

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests. Run rake lint to check the code style with Rubocop.

You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.