LCM from a prime factorisation (ILO 1, 2; 2 marks)

You have learned how to calculate lcm(a, b) using the prime factorisations of a and b. Your task is to complete the stub function lcm(a, b) to implement this behaviour. In your solution you should use the Python Counter class to represent a multiset, and make use of the included helper function prime_factors(n) to generate a list of prime factors for each input.

#%% Question 5: LCM from a prime factorisations

from collections import Counter

def lcm(a: int, b: int) -> int:

”’Returns lcm(a, b), calculated from their prime factorisations.”’

return None

#%% Provided functions for Question 5

from math import floor, sqrt

def primes(n):

”’Returns the set of primes between 2 and n, inclusive.”’

primes = {2} | set(range(3, n+1, 2)) #{2, odd numbers up to n}

for k in range(2, floor(sqrt(n)) + 1):

if k in primes:

primes.difference_update( range(k**2, n+1, 2*k) )

return primes

def primes_list(n):

”’Returns a sorted list of primes between 2 and n, inclusive.”’

return sorted(primes(n))

def prime_factors(n):

”’Returns the list of prime factors of n.”’

factors = []

iprimes = iter(primes_list(n))

while n > 1:

p = next(iprimes)

while n % p == 0:

n = n // p

factors.append(p)

return factors

# End of provided functions