Primes and Composite Numbers

A factor of a number divides into it exactly, leaving no remainder. To find every factor of 24, work upwards from 1 and test each number in turn. One times 24 works, so 1 and 24 are both factors. Two times 12 works, so add 2 and 12. Three eights, so add 3 and 8. Four sixes, so add 4 and 6. Five does not divide 24 exactly, so skip it. When you reach 6 you find 6 times 4, a pair you already have, and that is your signal to stop. Reading the pairs off gives eight factors: 1, 2, 3, 4, 6, 8, 12 and 24. Hunting in pairs like this means you never miss one.

Now count the factors. Twenty-four had eight of them, and any number with more than two factors is called composite. A number with exactly two factors, just 1 and itself, is called prime. Picture it as dots pushed into a rectangle. Seven dots only ever make a single line, one by seven, so 7 is prime. Twelve dots make one by twelve, two by six and three by four, so 12 is composite. Two cases catch everybody out. The number 1 has only one factor, itself, so it is neither prime nor composite. And 2 is prime — the only even prime there is, because every other even number picks up 2 as an extra factor.

Here is a way to find all the primes up to fifty without testing each one separately. It is called the Sieve of Eratosthenes. Cross out 1, because it is neither prime nor composite. Circle 2, then cross out every later multiple of 2. Circle the next number still standing, which is 3, and cross out every later multiple of 3. Do the same for 5, then for 7. Everything still standing is prime. You are left with fifteen primes below fifty: two, three, five, seven, eleven, thirteen, seventeen, nineteen, twenty-three, twenty-nine, thirty-one, thirty-seven, forty-one, forty-three and forty-seven. Notice how they thin out as the numbers grow larger.

Testing whether one number divides another does not always need long division. A number divides by 2 if its last digit is even. It divides by 5 if it ends in 0 or 5, and by 10 if it ends in 0. The clever ones use the digit sum: a number divides by 3 if its digits add to a multiple of 3, and by 9 if they add to a multiple of 9. So 126 divides by 3, because 1 plus 2 plus 6 is 9. For 4, look at the last two digits only — 116 ends in sixteen, which is a multiple of 4, so 116 is too. These tests turn a slow check into a single glance.

The biggest mistake in this topic is thinking odd means prime. Every prime above two is odd, but plenty of odd numbers are not prime. Nine is three threes. Twenty-one is three sevens. Twenty-five is five fives. Forty-nine is seven sevens. Fifty-one looks convincingly prime until you add its digits, get six, and realise three goes in — fifty-one is three times seventeen. Ninety-one is the champion trap: it survives the two, three and five tests and only falls to seven, because ninety-one is seven times thirteen. So run through two, three, five and seven in that order before you declare anything prime. That short routine catches almost everything you will meet this year.