# 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