Prime factorisation

Listing every factor works, but it gets long for numbers with many factors — and worse, you may MISS one, which gives a wrong answer with no warning. Can the process be made simpler and more reliable? It can, using prime factorisation.

Recall that a PRIME is a number greater than 1 that has only 1 and the number itself as factors. Last year you hunted for patterns among the primes up to 100 and met the Sieve of Eratosthenes.

Any number can be written as a product of primes: keep rewriting composite factors until only primes are left. That is its prime factorisation. For example, 90 = 3 × 3 × 2 × 5.

But 90 could have been split as 3 × 30, or 2 × 45, or several other ways. Do those lead to the same primes? Remarkably, yes — the resulting prime factors are ALWAYS the same, with perhaps a change of order. Follow 3 × 30 through: 90 = 3 × 30 = 3 × 2 × 15 = 3 × 2 × 3 × 5. The same primes, differently ordered.

One small case to note: the prime factorisation of a prime number is that prime itself. 7 factorises as 7.

There is a tidy way to carry it out, called the division method. Write the number, divide by a prime, write the quotient below, and repeat until the quotient is prime. For 105: divide by 3 to get 35, divide by 5 to get 7, and stop. Collect the primes down the left — 3 and 5 — together with the 7 at the bottom: 105 = 3 × 5 × 7.

The same for 30: divide by 2 to get 15, by 3 to get 5, and stop. So 30 = 2 × 3 × 5. Try 1200 this way, and compare it with hacking away at 1200 = 40 × 30 = 5 × 8 × 5 × 6 = … — the division method is far easier to keep straight.