Last updated at October 28, 2026 by Teachoo
Transcript
Question 5 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? Prime factorisation expresses a positive integer greater than 1 as a product of primes, including repeated factors. For example: 𝟏𝟖𝟎=𝟐 × 𝟐 × 𝟑 × 𝟑 × 𝟓 How we arrive at the algorithm From Question 4, we can find the distinct prime divisors. For each prime divisor, repeatedly divide it out. Count how many times the division succeeds. That count is its exponent in the factorisation. Algorithm to compute the prime factorisation of For each prime divisor, repeatedly divide it out. Count how many times the division succeeds That count is its exponent in the factorisation Algorithm to compute the prime factorisation of n Compute prime-divisors using primedivisors (𝑛). Set remaining to 𝑛. Start with an empty list prime-factorisation For each prime 𝑝 in prime-divisors Set exponent to 0 While 𝑝 divides remaining: Divide remaining by 𝑝 Increase exponent by 1 Add the pair (𝑝, exponent) to prime-factorisation Report prime-factorisation Example: Factorise 180 First find: Report prime-factorisation Example: Factorise 180 First find: primedivisors (𝟏𝟖𝟎)=[𝟐,𝟑,𝟓] Initially: remaining = 180. Process the prime 2 180.÷2=90 gives exponent 1. 90÷2=45 gives exponent 2. Now 45 is not divisible by 2 . Record: (𝟐,𝟐) Process the prime 3 45÷3=15 gives exponent 1. 15÷3=5 gives exponent 2. Now 5 is not divisible by 3. Record: (𝟑, 𝟐) Process the prime 5 5÷5=1 gives exponent 1. There’s nothing left. So, Record: (𝟓,𝟏) The result is: [(2, 2),(3, 2),(5, 1)] Therefore: 𝟏𝟖𝟎=𝟐^(𝟐) × 𝟑^(𝟐) × 𝟓^(𝟏) Question 5 (i) (i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this? Two suitable representations are: A list of repeated prime factors [2, 2, 3, 3, 5] This explicitly shows every occurrence. A list of prime-exponent pairs [(2, 2), (3, 2), (5, 1)] Here, each pair (𝒑,𝒆) means 𝒑^(𝒆) Let’s see how it looks like The prime–exponent representation is particularly useful for comparing two factorisations. The list [2,3,5] alone is not a complete representation of the prime factorisation of (180), because it omits multiplicities. Prime p | Exponent e | Factor represented 2 | 2 | 2^(2) 3 | 2 | 3^(2) 5 | 1 | 5^(1) Question 5 (ii) (ii) How would you compare the prime factorisations of two numbers? Represent each factorisation as a list of prime-exponent pairs. Then compare the exponents of matching primes. If a prime is absent from one factorisation, treat its exponent as 0. Example Consider: 180=2^(2) × 3^(2) × 5^(1) and 120=2^(3) × 3^(1) × 5^(1) Their representations are: 180:[(2, 2),(3, 2),(5, 1)] 120:[(2, 3),(3, 1),(5, 1)] [, ; , ] Compare them prime by prime 120:[(2, 3),(3, 1),(5, 1)] [, ; , ] Compare them prime by prime This shows which prime factors are common which appear in only one number, and how their multiplicities differ. Prime | Exponent in 180 | Exponent in 120 2 | 2 | 3 3 | 2 | 1 5 | 1 | 1