Algorithms · 4 marks

We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.

(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?

Answer: Represent a factorisation as a list of (prime, power) pairs in increasing order of the prime: 180 → [(2, 2), (3, 2), (5, 1)]. Build it by taking each prime p in primedivisors(n) and counting how many times p divides n. To compare two factorisations for the gcd, take each prime that appears in both lists with the smaller of its two powers; e.g. gcd(180, 750) = 2 × 3 × 5 = 30.

Step-by-step solution

Idea: A prime factorisation is a list of primes, each with a power. The primes come from primedivisors(n); the power of p is the number of times we can divide n by p before it stops dividing exactly. A common divisor can use each common prime at most as often as the smaller power allows.

(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?

Represent the factorisation as a list of pairs (prime, power), with the primes in increasing order:
180 = 2² × 3² × 5¹ → [(2, 2), (3, 2), (5, 1)].1 mark
Algorithm primefactorisation(n) (the algorithm the question asks for):
1. Start with an empty list factorisation.
2. For each prime p in primedivisors(n):
  – set count to 0 and value to n;
  – while p divides value, replace value by value ÷ p and add 1 to count;
  – add the pair (p, count) to factorisation.
3. Report factorisation.½ mark
Execute for 180: primedivisors(180) = [2, 3, 5]. p = 2: 180 → 90 → 45, count 2. p = 3: 180 → 60 → 20, count 2. p = 5: 180 → 36, count 1. Result [(2, 2), (3, 2), (5, 1)] ✓.½ mark

As a list of (prime, power) pairs in increasing order of the prime: [(2, 2), (3, 2), (5, 1)].

(ii) How would you compare the prime factorisations of two numbers?

Go through the two lists of pairs together (both are in increasing order of the prime, like the lists of divisors). For each prime p that appears in both lists, with powers a and b, take p to the smaller power, min(a, b). Primes that appear in only one list are left out.½ mark
The gcd is the product of these prime powers, because a common divisor can contain p at most min(a, b) times (more would not divide one of the numbers).½ mark
Example: 180 → [(2, 2), (3, 2), (5, 1)] and 750 = 2 × 3 × 5³ → [(2, 1), (3, 1), (5, 3)]. Common primes 2, 3, 5 with smaller powers 1, 1, 1: gcd(180, 750) = 2¹ × 3¹ × 5¹ = 30.1 mark
Two numbers are equal exactly when their lists are identical. Taking the larger power of every prime in either list gives the lcm instead: lcm(180, 750) = 2² × 3² × 5³ = 4500.

Match the primes in the two lists; for each prime in both, take the smaller power. The product of these is the gcd (e.g. gcd(180, 750) = 30). The larger powers of all primes give the lcm.

(i) As a list of (prime, power) pairs: 180 → [(2, 2), (3, 2), (5, 1)], built by counting how many times each prime divisor divides the number. (ii) Match the primes; for each prime in both lists take the smaller power; their product is the gcd (e.g. gcd(180, 750) = 30).

Check: 2² × 3² × 5 = 4 × 9 × 5 = 180 ✓. 180 ÷ 30 = 6 and 750 ÷ 30 = 25, with 6 and 25 sharing no factor, so gcd(180, 750) = 30 ✓.

Answer to write in the exam

(i)

180 = 2² × 3² × 5¹ → [(2, 2), (3, 2), (5, 1)] (list of (prime, power) pairs, primes increasing)

Algorithm primefactorisation(n):

1. factorisation = [ ]

2. For each prime p in primedivisors(n): count = 0, value = n; while p divides value: value = value ÷ p, count = count + 1; add (p, count) to factorisation

3. Report factorisation

180: p = 2 → 90, 45 (count 2); p = 3 → 60, 20 (count 2); p = 5 → 36 (count 1)

∴ 180 is represented as [(2, 2), (3, 2), (5, 1)]

(ii)

Compare the (prime, power) lists prime by prime.

For each prime p in both lists with powers a, b: take p^{min(a, b)}; ignore primes in only one list.

gcd = product of these prime powers.

e.g. 180 → [(2, 2), (3, 2), (5, 1)], 750 → [(2, 1), (3, 1), (5, 3)]

gcd = 2¹ × 3¹ × 5¹

∴ gcd(180, 750) = 30

Common mistakes that cost marks

Taking the larger power of each prime for the gcd. That gives the lcm.
Including a prime that appears in only one of the numbers (for example a 7) in the gcd.
Writing the factorisation as a list of primes without powers, [2, 3, 5]; then 180 and 30 would look the same.

How this can come in the exam

MCQ (1 mark)

Two numbers have prime factorisations [(2, 3), (3, 1), (7, 2)] and [(2, 1), (3, 2), (5, 1)]. Their gcd is

Show answer

(A) 6
Common primes 2 and 3; smaller powers 2¹ and 3¹. gcd = 6. (The numbers are 1176 and 90.)

Try one yourself

Write the prime factorisations of 504 and 540 as lists of pairs and use them to find gcd(504, 540).