## Quickly recognizing primes less than 100

Recently, Mark Dominus wrote about trying to memorize all the prime numbers under $1000$. This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a number under $1000$ is prime or composite? And can we make it clever enough to be done relatively quickly? This does tie into my other recent posts about primality testing, but to be clear, it’s also quite different: I am not talking about a general method for determining primality, but the fastest method we can devise for mentally determining, by hook or by crook, whether a given number under $1000$ is prime. Hopefully there are rules we can come up with which are valid for numbers less than $1000$—and thus make them easier to test—even though they aren’t valid for bigger numbers in general.

As a warmup, today I’ll write about how I determine whether a number less than 100 is prime: I don’t have them memorized, but can very quickly decide whether such a number is prime or not—and you can, too! This is a situation where doing a little mathematical analysis beforehand goes a long way.

Since $10^2 = 100$, every composite number less than $100$ has at least one factor which is less than $10$. This means that every composite less than $100$ is divisible by $2$, $3$, $5$, or $7$. Multiples of 2, 3, and 5 are relatively easy to recognize, and as we’ll see, $7$ is not hard to deal with either.

1. Any even number or multiple of 5 (i.e. numbers ending with an even number or with a 5) is clearly composite. (Other than 2 and 5 themselves, of course.)

2. Multiples of $3$ are composite. There are many numbers which I think of as “obvious” multiples of three: 9, 21, 27, and 33 because I have had their factorizations memorized since third grade; 81 because it’s a power of three so I have it memorized too; and 39, 63, 69, 93, and 99 because they consist of two digits each of which is a multiple of three. As you probably know, there is also a simple test for determining divisibility by three: just add the digits and see whether the result is divisible by three. This test identifies a few more “nonobvious” multiples of three which you might otherwise think are prime: $51 = 3 \cdot 17$, $57 = 3 \cdot 19$, and $87 = 3 \cdot 29$.

3. What’s left? There are only three numbers less than 100 which are composite and not divisible by 2, 3, or 5:

• $49 = 7 \cdot 7$ and $77 = 7 \cdot 11$ are easy to spot.
• $91 = 7 \cdot 13$ is the one I always used to forget about—I call it a “fool’s prime” because it “looks” prime but isn’t. It’s worth just memorizing the fact that it is composite (and its factorization).

So, to sum up, faced with a number less than 100 that I want to test for primality, I can quickly rule it out if it is divisible by 2, 3, or 5, or if it is a multiple of 7 I recognize (49, 77, or 91). And that’s it! Anything else has to be prime.

In a future post I plan to write about how feasible it is to come up with a similar procedure to identify all primes under 1000.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, primes and tagged , , , . Bookmark the permalink.

### 17 Responses to Quickly recognizing primes less than 100

1. Yes, that’s how I’ve always thought about the primes under 100. There’s a divisibility test for 7, but I don’t use it often since the time I had to prove it about 10 years ago. The one for 11 is easy. I remember when looking into the one for 7 that there’s some principle that can lead from that to tests for 13, 17, etc., but I don’t think I understood it at the time and definitely don’t remember it. 😦

• Brent says:

Indeed, which divisibility test for 7 are you thinking of? There are a few I know of. I do also know about divisibility tests for bigger primes, which will come up when I write about testing numbers under 1000 for primality — stay tuned!

• Mark Dominus says:

I did recently post [an article about testing for divisibility by 7](https://blog.plover.com//math/divisibility-by-7.html). I have a followup in the works with additional tricks, but testing for divisibility by 7 is pretty easy and is not the issue with mental identification of primes under 1000. The problem is with numbers like 851.

• Joe says:

851 = 900 – 49 = (30+7)(30-7)

2. Joe says:

91 is also of the form a^2 – b^2, for small b.

• Brent says:

Oh, nice observation!

3. j2kun says:

I would be interested to see an machine learning approach designed to overfit. Pick a small set of features (the digits of the number) and a decent set of human-computable transformations (“add”, “multiply”, “is divisible by k”, “equals k”), and then find small decision trees that get 95+% classification rate, memorizing the remaining <= 50 composites.

Is this similar to what you had in mind?

• j2kun says:

er– for decision trees you’d have to compute all the features in advance. Could also try small branching programs, or a really small neural network…

• Brent says:

Yes, this is exactly the sort of thing I had in mind, though at this point I hadn’t got much farther than thinking there should be a way to pick some features and run an algorithm to build small decision trees. A straightforward approach is to run through divisibility tests up to 13 and then memorize the ~25 remaining composites which are products of primes >= 17; I’m curious to see whether we can come up with something better using an approach like what you outline. Would you be interested in collaborating on this? I’m not very familiar with machine learning techniques beyond the basics.

4. Joe says:

A composite approach may work best. Check for factors up to, say, 13, and also check a^2 – b^2 for small b, say up to 13. This would give you every number up to 799 (47×17), with no memorization needed, other than squares.

• Joe says:

If you make that b <= 18, then all numbers up to 1000 are checked by applying those two procedures. There are some short cuts in checking whether it’s of the form a^2 – b^2, so it can be done quite quickly (and memorizing squares is easier and a lot more useful than memorizing the factors of numbers like 851).

• Brent says:

Interesting! Can you explain the short cuts you refer to (or give a link to some explanation)?

5. joe says:

Take 851 as an example. You don’t need to successively add 1, 4, 9, 16, … and see whether you have a square each time. Rather you can subtract it from 900, 961, 1024, … and see whether that is a square. (The first one you try is.) Further, this sequence terminates quickly as you have tried direct division up to 13, so if it is composite a-b must be at least 17. This no longer happens after a is 34, so you settle primality with at most five subtractions.
The two methods complement each other because direct division works quickly if there is a small factor, and difference of two squares works well when the two factors are close together. There are very few composite numbers under 1000, which aren’t one or the other, and none at all if you divide up to 13, and then check a^2 – b^2 for b up to 18.

6. Joe says:

Another short cut is to use the fact that the difference of successive squares increases by 2 each time. So in the previous example, if 900 – 851 isn’t a square, you add 61, then 63, then 65, etc until you get a square or get over 324. That way you only have to memorize the first 18 squares, which you probably already know.

7. Joe says:

One final comment: if you first verify there is no factor of 13 or less, then capping b at 15 is sufficient to establish primality for every number up to 1000 with the sole exception of 901.

This site uses Akismet to reduce spam. Learn how your comment data is processed.