Python Code Example: least common multiple

This code snippet defines two functions: one to calculate the Greatest Common Divisor (GCD) using the Euclidean algorithm and another to calculate the Least Common Multiple (LCM) using the GCD.

Code Example

def gcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a > b:
        return gcd(a - b, b)
    else:
        return gcd(a, b - a)


def lcm(a, b):
    return a * b / gcd(a, b)


a, b = 20, 8

print("Least common multiple is: " + str(lcm(a, b)))

Output

Least common multiple is: 40.0

Code Explanation

Function gcd(a, b)

def gcd(a, b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a > b:
        return gcd(a - b, b)
    else:
        return gcd(a, b - a)

• Purpose: This function calculates the GCD of two integers a and b.
• Parameters: The function takes two parameters:
  • a: The first integer.
  • b: The second integer.
• Base Cases:
  • if a == 0: If a is 0, the GCD is b. This is because the GCD of 0 and any number b is b.
  • elif b == 0: If b is 0, the GCD is a. Similarly, the GCD of 0 and any number a is a.
• Recursive Cases:
  • elif a > b: If a is greater than b, the function calls itself with a - b and b. This step reduces the value of a by subtracting b from it.
  • else: If b is greater than or equal to a, the function calls itself with a and b - a. This step reduces the value of b by subtracting a from it.

This process continues recursively until one of the base cases is met, effectively reducing the problem size at each step.

Function lcm(a, b)

def lcm(a, b):
    return a * b / gcd(a, b)

• Purpose: This function calculates the Least Common Multiple (LCM) of two integers a and b.
• Parameters: The function takes two parameters:
  • a: The first integer.
  • b: The second integer.
• Calculation:
  • The function uses the formula LCM(a,b)=a×bGCD(a,b)LCM(a,b)=GCD(a,b)a×b​.
  • It multiplies a and b and then divides the product by the GCD of a and b, which is calculated using the gcd function.

Main Program

a, b = 20, 8

• Variable Initialization: Two variables a and b are initialized with the values 20 and 8 respectively.

print("Least common multiple is: " + str(lcm(a, b)))

• Function Call and Output:
  • The lcm function is called with a and b as arguments.
  • The result, which is the LCM of 20 and 8, is converted to a string and concatenated with the message “Least common multiple is: “.
  • This message is printed to the console.

Example Execution

For lcm(20, 8), the function will perform the following steps:

1. Calculate GCD: gcd(20, 8)
   • 20 > 8, so it calls gcd(20 - 8, 8) which is gcd(12, 8).
   • 12 > 8, so it calls gcd(12 - 8, 8) which is gcd(4, 8).
   • 4 < 8, so it calls gcd(4, 8 - 4) which is gcd(4, 4).
   • 4 == 4, so it calls gcd(4, 4 - 4) which is gcd(4, 0).
   • Since b == 0, it returns 4.
2. Calculate LCM: lcm(20, 8)
   • Using the formula LCM(20,8)=20×8 /GCD(20,8)
   • Substituting the values: LCM(20,8)=20×8/4=40