Quickly recognizing primes less than 100

Posted on September 16, 2018 by Brent

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.

About Brent

Associate 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.

18 Responses to Quickly recognizing primes less than 100

  1. Michael Paul Goldenberg says:
    September 16, 2018 at 11:07 pm

    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. 😦

  2. Joe says:
    September 17, 2018 at 6:13 am

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

  3. j2kun says:
    September 17, 2018 at 9:03 am

    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:
      September 17, 2018 at 9:05 am

      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:
      September 17, 2018 at 11:33 am

      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:
    September 17, 2018 at 11:19 pm

    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:
      September 18, 2018 at 12:37 am

      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).

  5. joe says:
    September 18, 2018 at 9:43 am

    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:
    September 18, 2018 at 11:00 am

    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:
    September 19, 2018 at 2:15 am

    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.

  8. Pingback: Quickly recognizing primes less than 1000: divisibility tests | The Math Less Traveled

  9. Christy McGuire says:
    October 20, 2018 at 3:10 pm

    Thank you! My Dyslexic child is learning to divide by factoring rather than by the traditional algorithm, and this will be a huge help.

Comments are closed.