Euclidean

• used to find gcd - Greatest common divisor

Python

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

# Optimized
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

tip

To find LCM: $a * b = gcd * lcm$