Codility - Lesson 12 Euclidean Algorithm

Source Link:
https://codility.com/programmers/lessons/12-euclidean_algorithm/

Wikipedia:
https://en.wikipedia.org/wiki/Euclidean_algorithm

Some notes:
The Euclidean algorithm solves the problem of computing the greatest common divisor (gcd) of two positive integers.

12.2. Euclidean algorithm by division

For two given numbers a and b, such that a >= b:
• if b | a, then gcd(a, b) = b,
• otherwise gcd(a, b) = gcd(b, a mod b).

Notice that we can recursively call a function while a is not divisible by b.

12.2: Greatest common divisor by dividing.
1 def gcd(a, b):
2 if a % b == 0:
3 return b
4 else:
5 return gcd(b, a % b)

12.4. Least common multiple

The least common multiple (lcm) of two integers a and b is the smallest positive integer that
is divisible by both a and b. There is the following relation:


Knowing how to compute the gcd(a, b) in O(log(a+b)) time, we can also compute the lcm(a, b)
in the same time complexity.