Problem 1. Write a function LCM(a, b)
that returns the least common multiple of integers a
and b
. Avoid computing any products bigger than LCM(a, b)
itself (big products may cause overflow errors in many languages; in others, like Python, they can cause slower computation).
If either a = 0
or b = 0
, we define LCM(a, b) = 0
.
Hint: Use the formula based on the prime factorization of a number.
Problem 2. Write a function LCM(L)
that returns the least common multiple of all the elements in list L
. Avoid computing any products bigger than LCM(L)
itself.
If either of the elements in L
is a zero, we define LCM(L) = 0
.
Hint: Use the formula based on the prime factorization of a number.
Note: Make sure that the function works properly for any list L
, including an empty one (this should raise an appropriate error).
Problem 2a. Try to write LCM
in a way that it can be invoked by an arbitrary number of arguments, i.e., LCM(a)
, LCM(a, b)
, LCM(a, b, c)
, etc.
Note: Problem 2a is not covered in the course materials and, as such, it requires some Googling efforts. It will not be a part of the tests.
Problem 3a. What is the worst-case complexity of
Problem 3b. Assume that you have an unsorted list. Which of the following is faster and why?