Algorithm to find the prime factorisation of n (for n≥2)
-
Start with an empty list factors, and set p to 2.
-
If n=1, report factors and stop.
-
If p divides n: replace n by n÷p, and record one more factor p in factors (if p is already in factors, increase its count by 1; otherwise add p with count 1). Repeat from Step 2 with the same p.
-
Otherwise, increase p by 1 and repeat from Step 2.
Each p that divides is prime: by the time we reach p, all smaller primes have already been divided out completely, so a composite p (like 4 or 6) can never divide what is left.
Executing it for 180:
-
2 divides 180: 180÷2=90, so record one factor 2.
-
2 divides 90: 90÷2=45, so record one factor 2.
-
2 does not divide 45: try the next number, 3.
-
3 divides 45: 45÷3=15, so record one factor 3.
-
3 divides 15: 15÷3=5, so record one factor 3.
-
3 does not divide 5: try the next number, 4.
-
4 does not divide 5: try the next number, 5.
-
5 divides 5: 5÷5=1, so record one factor 5.
-
Now n=1, so we stop.
The factors are 2 (twice), 3 (twice) and 5 (once): 180=22×32×51.
(i) We can represent the factorisation as a list of pairs (prime, power), with the primes in increasing order:
180→[(2,2),(3,2),(5,1)]
Each pair says which prime occurs and how many times. (Another way is a list of powers for the primes 2, 3, 5, 7, … in order: [2, 2, 1] for 180.)
(ii) Since both lists are in increasing order of primes, we compare them by scanning them together, as in merging two sorted lists (Exercise Set 11.2, Question 1). At each step look at the current prime p in the first list and q in the second:
-
If p=q, the prime occurs in both numbers; compare the two powers, then move on in both lists.
-
If p<q, the prime p occurs only in the first number; move on in the first list.
-
If p>q, the prime q occurs only in the second number; move on in the second list.
This tells us everything: the two numbers are equal if the lists are identical; the first divides the second if every prime of the first appears in the second with at least the same power; and the gcd is the product of the primes common to both, each raised to the smaller of its two powers (the lcm uses every prime with the larger power).
Example: 180→[(2,2),(3,2),(5,1)] and 825=3×5×5×11→[(3,1),(5,2),(11,1)].
Scanning: 2 is only in 180; 3 is in both, with powers 2 and 1, smaller is 1; 5 is in both, with powers 1 and 2, smaller is 1; 11 is only in 825. So
gcd(180,825)=31×51=15