SoFunction
Updated on 2025-03-10

Code examples and solutions for finding the minimum common multiple and greatest common divisor in Python

Several solutions to the minimum common multiple

Method 1

Code ideas

  • Enter parameters: Receive two integersmandn。
  • Determine the larger value:judgemandnWhich one is larger, store the larger value in the variablebiggermiddle.
  • Find the smallest common multiple：
    • Use onewhile cycle，from biggerStart to increase continuously.
    • In each loop, check the current onebiggerCan it be simultaneouslymandnDivide.
    • If possible, return to the current onebiggerAs the least common multiple.
    • If not, thenbiggerIncrease 1 and continue the next cycle.
  • Output result: Call the function and print the minimum common multiple
    def f1(m, n):  
    # Determine the larger values ​​in m and n    if m > n:  
        bigger = m  
    else:  
        bigger = n  
      
    # Start with a larger value, constantly incrementing, looking for the smallest common multiple    while True:  
        # Check whether the current bigger can be divided by m and n at the same time        if bigger % m == 0 and bigger % n == 0:  
            # If possible, return the current bigger as the minimum common multiple            return bigger  
        else:  
            # If not, increase the bigger by 1 and continue the loop            bigger += 1  
  
# Call the function and print the result# Example: Calculate the minimum common multiples of 23 and 74print("%d is the least common multiple" % f1(23, 74))

Method 2

Code ideas

  • Enter parameters: Receive two integersmandn。
  • Determine the larger value:judgemandnWhich one is larger, store the larger value in the variablebiggermiddle.
  • Find the smallest common multiple：
    • Initialize a counteriis 1.
    • Use onewhileCycle, increasing continuouslyi。
    • In each loop, calculatebigger * i, and check whether this value can be simultaneouslymandnDivide.
    • If possible, returnbigger * iAs the least common multiple.
    • If not, continue with the next loop.
  • Output result: Call the function and print the minimum common multiple.
def f2(m, n):  
    # Determine the larger values ​​in m and n, as the starting point to reduce some unnecessary multiplication operations    if m > n:  
        bigger = m  
    else:  
        bigger = n  
      
    # Initialize the counter i    i = 1  
      
    # Start from 1 and continue to increase, looking for the smallest common multiple    while True:  
        # Calculate the value of the current bigger * i        current_value = bigger * i  
          
        # Check whether the current current_value can be divided by m and n at the same time        if current_value % m == 0 and current_value % n == 0:  
            # If possible, return the current current_value as the minimum common multiple            return current_value  
        else:  
            # If not, increase counter i by 1 and continue looping            i += 1  
  
# Call the function and print the result# Example: Calculate the minimum common multiples of 23 and 74print("%d is the least common multiple" % f2(23, 74))

Method 3

Code ideas

  • Importing math module：mathThe module provides many mathematical functions, including functions that calculate the greatest common divisor (GCD) and the least common multiple (LCM).
  • Using functions: Directly callFunctions to calculate the minimum common multiple of two numbers and print the result.
  • Calculate LCM using GCD: According to the relationship between the least common multiple and the greatest common divisor,LCM(a, b) = abs(a * b) // GCD(a, b), to calculate the minimum common multiple of two numbers and print the result. Dividing operator is used here//to make sure the result is an integer.
import math  
  
# Use functions to calculate the minimum common multiples of 23 and 74 and print the resultprint("%d is the least common multiple" % (23, 74))  
  
# Calculate LCM using GCD# According to the formula LCM(a, b) = abs(a * b) // GCD(a, b)# Calculate the absolute value of the product of 23 and 74 (although 23 and 74 are positive here, the absolute value is not necessary, but for generality you can add it)# Then divide by their greatest common divisor to get the least common multiplelcm_using_gcd = abs(23 * 74) // (23, 74)  
# Print the resultsprint("%d is the least common multiple" % lcm_using_gcd)

Several solutions to the greatest common divisor

Method 1

Code ideas

  • Enter parameters: Receive two integersmandn。
  • Determine the smaller value:judgemandnWhich is smaller, storing smaller values ​​in variablessmallermiddle.
  • Find the greatest common divisor：
    • fromsmallerDecreases to 1.
    • In each loop, check whether the current number can be simultaneouslymandnDivide.
    • If possible, return this number as the greatest common divisor.
    • If not, continue with the next loop.
  • Output result: Call the function and print the greatest common divisor
def f1(m, n):  
    # Determine the smaller values ​​in m and n    if m < n:  
        smaller = m  
    else:  
        smaller = n  
      
    # Decrement from smaller to 1, find the greatest common divisor    for i in range(smaller, 0, -1):  # Note that the step size here is -1, indicating decreasing        # Check whether the current i can be divided by m and n at the same time        if m % i == 0 and n % i == 0:  
            # If possible, return i as the greatest common divisor            return i  
  
# Call the function and print the result# Example: Calculate the greatest common divisors of 12 and 36print("%d is the greatest common divisor" % f1(12, 36))

Method 2

Code ideas

  • Enter parameters: Receive two integersmandn。
  • Determine the smaller value:useminFunction findingmandnThe smaller value in the variablesmallermiddle.
  • Find common divisors：
    • Initialize an empty listfto store the common divisor found.
    • useforLoop traversal from 1 tosmallerall integers.
    • In each loop, check whether the current integer can be simultaneouslymandnDivide.
    • If possible, add this integer to the listfmiddle.
  • Return the maximum common divisor:usemaxFunction Find Listfand return it.
  • Output result: Call the function and print the returned maximum common divisor.
def f2(m, n):  
    # Determine the smaller values ​​in m and n    smaller = min(m, n)  
      
    # Initialize an empty list to store common divisors    f = []  
      
    # traverse all integers from 1 to smaller    for i in range(1, smaller + 1):  
        # Check whether the current integer can be divided by m and n at the same time        if m % i == 0 and n % i == 0:  
            # If possible, add this integer to list f            (i)  
      
    # Returns the maximum value in list f, that is, the maximum common divisor    return max(f)  
  
# Call the function and print the maximum common divisor returned# Example: Calculate the greatest common divisors of 12 and 36print("%d is the greatest common divisor" % f2(12, 36))

Method 3 (Turning and turning phase division)

Code ideas：

  • Input check and adjustment：
    • functionf1Receive two integersmandnAs input.
    • To ensuremNot less thann,likemLess thann, the two are exchanged.
  • Calculate the greatest common divisor：
    • usewhileCirculation, conditionalnNot 0.
    • Inside the loop, unpacking with tuples is updated simultaneouslymandnValue:mAssigned as the current valuen,andnBe assigned asm % n(Right nowmDivide bynremainder of ).
    • This process will continue to iterate untilnChange to 0.
  • Return result：
    • whennWhen it is 0,mThe stored in the function is the greatest common divisor to be requested, and the function returnsm。
def f3(m, n):  
    # If m is less than n, exchange the values ​​of m and n to ensure that m is not less than n (this step is optional)    if m < n:  
        m, n = n, m  # Use tuple unpacking for value exchange      
    # When n is not 0, continuous loop calculation    while n:  
        #Use tuple unpacking to update the values ​​of m and n at the same time        # m is updated to the current n, n is updated to the remainder of m divided by n        m, n = n, m % n  
      
    # When n is 0, m is the greatest common divisor to be found    return m  
  
# Call function f3 and print out the greatest common divisors of 12 and 24print(f3(12, 24))  # The output result should be12

Method 4

In Python,mathThe module provides agcdThe function of the function can efficiently calculate the greatest common divisor of two or more integers (GCD, Greatest Common Divisor)

import math  
  
# Call function to calculate the greatest common divisors of 3139 and 2117result = (3139, 2117)  
  
# Print the resultsprint(result)

Summarize

This is the article about finding the minimum common multiple and greatest common divisor in Python. For more relevant content on Python, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!