Home

> urticator.net
  Search

  About This Site
> Domains
  Glue
  Stories

  Computers
  Driving
  Games
  Humor
  Law
  Math
> Numbers
  Science

  Powers and Fractions
  Notes About Squares
  Decimal Expansions
  Repeat Length Again
  Number Maze
> Primes
  Divisibility
  Intrinsic Nature of Primes
  Other Topics
  Other Topics (2)

  Three Digits
  Four Digits
  The Standard Series

Primes

I think of myself as knowing the primes up to about 50.

2 3 5 7   11 13 17 19   23 29   31 37   41 43 47

For most purposes, that's way more than enough. Recently, though, I had a small insight, and realized that (a) I could already recognize all the primes up to 100, and (b) it would be pretty easy to learn to recognize primes up to 200, 300, or more. So, right at the moment, that's what I'm doing … learning. (Although, who knows if I'll remember any of it a year from now.)

To explain the insight, I think it will help to review the standard method of testing primality. So, suppose you're wondering whether some number n is prime. What do you do?

  • First, of course, you look at the last digit to see if the number is a multiple of 2 or 5. (I take that action so much for granted that I can hardly imagine “wondering” whether such a number is prime.)
  • Next, you add up the digits to see if the number is divisible by 3.
  • Finally, you try dividing by other known primes p, in order, starting with 7 and stopping when p2 > n (because if n has more than one factor, at least one of them must be less than or equal to root n). Actually, as explained in Divisibility, it's easier to compute n mod p than to divide n by p, but that's just a detail.

The first two steps are the same as the first three iterations in the famous sieve of Eratosthenes. At that point, the sieve repeats with length 30. Here's what it looks like if you write the numbers in rows of ten, leaving out the even numbers entirely.

The boxes represent potential primes, numbers that have not been excluded.

Now, here's the insight. Up to surprisingly large values of n, most potential primes are actual. So, if you want to learn to recognize primes, it's easiest to treat primes as the rule, and learn the exceptions, i.e., the composite numbers.

In other words, there aren't a lot of composite numbers that have prime factors that are all at least 7.

Here's a table of the sieve pattern for numbers up to 600.

Not only are there not a lot of composite numbers, almost all of them have only two factors. The two exceptions are marked with red Xs.

343 = 7 × 7 × 7
539 = 7 × 7 × 11

The first you might recognize as a power of 7; the second you probably just have to learn (if you want to be able to recognize primes in that range).

The other composite numbers, the ones with two factors, can be written down as a multiplication table.

7111317192329313741
7497791119133161203217259287
11-121143187209253....
13--169221247299....
17---289......

I've only included numbers up to 300, to make it less intimidating, but of course you can extend it as far as you want.

It's especially easy to recognize the composite numbers up to 100 … all you have to do is recognize 49 and 77 as composite (duh) and remember that 91 = 7 × 13. The latter fact has been familiar to me for a long time, but a mathematician friend of mine claims that people do often mistake 91 for a prime, so I guess I shouldn't take it for granted.

So, to summarize, the new method is the same as the standard one, except that there's one more step before the trial division.

  • If the number is within the range that you know about, and you don't immediately recognize it as composite, then it's prime.

By the way, it's definitely better to learn the multiplication table than to just memorize a list of composite numbers. Then, not only can you recognize primes, but if you can divide by 2, 3, and 5 quickly, you can factor any number in range almost instantly (and lots of other numbers, too).

next

 

  See Also

  Dead Reckoning
  Four Digits
  In Mathematics
  In Other Bases
  Intrinsic Nature of Primes
  Multiplication in Base 10
  Multiplication Table, The
  Next Block, The
  Number Line
  Other Bases
  Other Methods
  Reduction Rules
  Squares
  Sums of Squares
  Three Digits

@ July (2004)
  November (2004)