Python: Least common multiple (LCM) of two positive integers

Last update on December 21 2024 07:22:31 (UTC/GMT +8 hours)

LCM Calculator

Write a Python program to find the least common multiple (LCM) of two positive integers.

From Wikipedia,
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0) as 0 for all a, which is the result of taking the lcm to be the least upper bound in the lattice of divisibility.

Pictorial Presentation:

Sample Solution-1:

Python Code:

# Define a function 'lcm' that calculates the least common multiple (LCM) of two numbers, 'x' and 'y'.
def lcm(x, y):
    # Compare 'x' and 'y' to determine the larger number and store it in 'z'.
    if x > y:
        z = x
    else:
        z = y
    
    # Use a 'while' loop to find the LCM.
    while True:
        # Check if 'z' is divisible by both 'x' and 'y' with no remainder.
        if (z % x == 0) and (z % y == 0):
            # If both conditions are met, 'z' is the LCM, so store it in 'lcm' and break the loop.
            lcm = z
            break
        # If the conditions are not met, increment 'z' and continue checking.
        z += 1
    
    # Return the calculated LCM.
    return lcm

# Calculate and print the LCM of 4 and 6.
print(lcm(4, 6))
# Calculate and print the LCM of 15 and 17.
print(lcm(15, 17))

Sample Output:

12
255

Explanation:

The said code defines a function "lcm(x, y)" that takes two integers as its argument and will return the least common multiple (LCM) of two arguments, "x" and "y".

First, the function determines which number is larger and assigns that value to a variable named "z". It then enters a loop that continues indefinitely (while(True)) until the LCM is found.

Inside the loop, the code checks if the current value of "z" is divisible by both "x" and "y" (if((z % x == 0) and (z % y == 0))). If it is true then the LCM is assigned to the variable "lcm" and the loop is broken. Otherwise, the value of "z" is incremented by 1 and the check is repeated.

Finally, the function returns the value of "lcm" as the output.

After the function definition, the code calls the function twice, first with the arguments 4 and 6, then with the arguments 15 and 17 and prints the results.

Flowchart:

Sample Solution-2:

Use functools.reduce(), math.gcd() and lcm(x,y) = x * y / gcd(x,y) over the given list.

Python Code:

# Import the 'reduce' function from the 'functools' module and the 'gcd' function from the 'math' module.
from functools import reduce
from math import gcd

# Define a function 'lcm' that calculates the least common multiple (LCM) of a list of 'numbers'.
def lcm(numbers):
    # Use the 'reduce' function to apply a lambda function that calculates the LCM for a pair of numbers.
    # The lambda function multiplies two numbers and divides the result by their greatest common divisor (gcd).
    # This process is applied cumulatively to all numbers in the list.
    return reduce((lambda x, y: int(x * y / gcd(x, y))), numbers)

# Calculate and print the LCM of the numbers in the list [12, 7].
print(lcm([12, 7]))
# Calculate and print the LCM of the numbers in the list [1, 3, 4, 5].
print(lcm([1, 3, 4, 5]))
# Calculate and print the LCM of the numbers in the list [4, 6].
print(lcm([4, 6]))
# Calculate and print the LCM of the numbers in the list [15, 17].
print(lcm([15, 17]))

Sample Output:

84
60
12
255

Explanation:

The said code imports the "reduce" function from the "functools" module, and the "gcd" function from the "math" module, then it defines a new function "lcm(numbers)" that takes a list of integers as input and returns the least common multiple (LCM) of all the integers in the list using the "reduce" function.

The function uses lambda function that takes two integers as input and returns the LCM of the two integers using the formula LCM(x,y) = (x*y)/gcd(x,y) and gcd function from math library to calculate the GCD.

The "reduce" function applies the lambda function cumulatively to the elements of an iterable (in this case, the list of integers) so as to reduce the iterable to a single value.

At the end, the function is called with different inputs and prints the LCM of the inputs.

Flowchart:

Python Code Editor:

Previous: Write a Python program to compute the greatest common divisor (GCD) of two positive integers.
Next: Write a Python program to sum of three given integers. However, if two values are equal sum will be zero.