How to find the greatest common divisor and least common multiple in Python

How to find the greatest common divisor and least common multiple in python

1. Find the greatest common divisor

The algorithm for finding the greatest common divisor using the euclidean division method is as follows:

Two positive integers a and b (a>b), their greatest common divisor is equal to the remainder of a divided by b between c and b Greatest common divisor. For example, if 25 is divided by 10, the quotient of 2 is 5, then the greatest common divisor of 10 and 25 is equal to the greatest common divisor of 10 and 5.

The specific code is as follows:

def gongyue(a, b):
    """
    欧几里得算法----辗转相除法
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    # 如果最终余数为0 公约数就计算出来了
    while(b!=0):
        temp = a % b
        a = b
        b = temp
    return a

2. Find the least common multiple

After finding the greatest common divisor of a and b, use gongbei (a,b) = (a*b)/gongyue(a,b) Calculate the least common multiple of two numbers:

# 求两个数的最小公倍数
def gongbei(a,b):
    return a * b / gongyue(a, b)

Recommended learning: Python video tutorial

The above is the detailed content of How to find the greatest common divisor and least common multiple in Python. For more information, please follow other related articles on the PHP Chinese website!