About This Site
Powers and Fractions
Notes About Squares
Repeat Length Again
Intrinsic Nature of Primes
Other Topics (2)
PrimesI 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?
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
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.
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.
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).
In Other Bases
Intrinsic Nature of Primes
Multiplication in Base 10
Multiplication Table, The
Next Block, The
Sums of Squares
@ July (2004)