eoogbe/prime_table

A web app that displays a multiplication table of prime numbers

Prime Table

This web application displays a multiplication table of prime numbers.

It takes in a numeric input n from the user an outputs a multiplication table of n prime numbers.

How to run it

This app uses Ruby v3.1.2 and runs well in the latest Chrome browser.

To install dependencies, run:

$ bundle

The database is PostgreSQL. To create the database, run:

$ bin/rake db:create db:schema:load

To run the development server:

$ bin/dev

Navigate to http://localhost:3000 to view the app.

To run the Ruby tests:

$ bin/rspec

To run the JS tests:

$ yarn test

What I'm pleased with

I think this is a pretty clean, easy to follow application. The logic is divided up in sensible ways in idomatic places.

What I would do if I had more time

• Convert each number in the table into a link to a new prime table for that number as n (Issue #3)
• Support n > 1000 on the client. (Currently just works on the server.) (Issue #6)

Structure

This app is made using Ruby on Rails. The list of primes is generated server-side through the route /primes.json and the multiplication table itself is generated on the client using Typescript.

Prime Generation

The prime numbers are generated in app/models/prime_generator.rb using the Sieve of Eratosthenes, which runs in O(n log(log(n))) time. Since we don't know how high of a prime the nth prime is, we make successively larger guesses until we get it right. A more efficient algorithm would be Euler's Sieve, which runs in O(n) time and does not need repeated guessing. However this algorithm uses modolus, which is not allowed for the exercise.

An ActiveRecord model Prime saves previously generated primes in the database to remove the need to regenerate them on successive requests.

Multiplication Table Generation

The client side generates the multiplication table in batches of 100 on each animation frame. The implementation is in app/javascript/primeTable.ts. By breaking the generation up into multiple batches, we can generate larger numbers. Unfortunately there is a limitation on the size of n. The app does not handle displaying a table for n above 1000 very well. The /primes.json route, however, can handle generating primes for much larger numbers. (It can generate 1,000,000 primes in about 130s.)

prime_table's Issues

Add CSS styling

Add link to prime table for a number from every number in table

A possible extension could be adding a link to the next prime table for every number in the table. So for example, if the table looks like this:

	2	3	5
2	4	6	10
3	6	9	15
5	10	15	25

Then I could click on the number 10 and it'd take me to a page with the prime table for the first 10 prime numbers.

Add input validation

A robust app would not assume that the input will be perfect. A nice-to-have would be input validation. Validation should happen on the server and in the client. I'd like to validate:

• Input int is a valid int
• Input int is at least 1

Client cannot generate n larger than 1000

While the server can output very large n (up to 1,000,00 has been tested), the client cannot generate a multiplication table for n larger than 1000. It would be better if the client were more robust.