How Many Prime Numbers in a Grid Full of Digits?

Ray Tracing - Project #8 - Kevin Wall

I started another community programming puzzle over on Codingame.com yesterday. One of the first problems I ran into was determining how much storage space I would need. Writing down my thoughts sometimes helps clarify the issue, and since the editor on the Codingame IDE doesn't have automatic word wrap, nor does the brain dead Linux text editor, I used what was handy, which was Blogger. Plus I got a blog post out of it.

The problem is straight forward enough: We are given a grid filled with numeric digits. Our job is to find out how many prime numbers we can find in this grid.

Since maximum size of the grid is 8 by 8, none of our numbers can have more than 8 digits. The standard storage space for an integer is 32-bits. Leave off one bit for the sign (positive or negative) and the largest number you can store in this space is two billion and something, which has 10 digits, so a standard integer should do fine for all of our work.

The grid has R rows and C columns, so there can be at most R x C single digit prime numbers, but less than ten, because there are only ten digits, and actually only 4, because there are only 4 single digit prime numbers: 2, 3, 5 & 7.

An R by C grid can have at most:

• ((R - 1) x C) + (R x (C - 1)) two digit prime numbers.

An 8 by 8 grid can have:

• (7 x 8) + (8 x 7)                   two digit prime numbers.
• (6 x 8) + (8 x 6), or (2 x 8 x 6) three digit prime numbers.
•                       (2 x 8 x 5)  four digit numbers

Continuing the pattern, the total comes out to (2 x 8 x 7!) or 80,640. Would is be possible to generate a grid that had that many unique prime numbers? That's another question and given that even if we only need four bytes for each number, we are going to need less than half a megabyte of RAM, so we don't need to go any further, we'll just allocate space for 80,640 integers.

It is a relatively simple programming problem, but the boss lady was on a rampage yesterday so my concentration was impaired. Also, I was a little out of practice since I hadn't done any programming for several weeks. In particular, I wasn't able to put together a simple procedure to determine if a number was prime. I figured out the solution this morning. Turns out you need to hold TWO coherent thoughts in your head in order to make it work. One thought is not sufficient.