欢迎访问宙启技术站
智能推送

Python函数:计算两个数的最大公因数和最小公倍数

发布时间:2023-06-14 01:00:09

1. 最大公因数

最大公因数是指两个或多个数公有的约数中最大的一个数。常见的求最大公因数的方法有辗转相除法、质因数分解法、更相减损法等。

辗转相除法:

如果说a和b是两个正整数,并且a>b,那么我们可以用a除以b得到一个商q和一个余数r=q*b,如果余数r是0,那么b就是它们的最大公因数;否则,我们可以把b作为被除数,r作为除数,再进行一次相除,如此下去,直到余数为0,此时的除数就是它们的最大公因数。

以下是辗转相除法的Python代码:

def gcd(a,b):

    if b == 0:

        return a

    else:

        return gcd(b,a%b)

其中,a和b分别是待求最大公因数的两个正整数,函数返回的就是它们的最大公因数。该代码也适用于多个正整数求最大公因数的情况,只需要把最后一个参数改成a%b即可。

2. 最小公倍数

最小公倍数是指两个或多个数公有的倍数中最小的一个数。给定两个正整数a和b,那么它们的最小公倍数可以通过如下公式求得:

lcm(a,b) = a*b / gcd(a,b)

其中gcd(a,b)是a和b的最大公因数。

以下是计算任意多个正整数的最小公倍数的Python代码:

def lcm(*nums):

    result = 1

    for num in nums:

        result *= num // gcd(result, num)

    return result

其中,nums是任意个正整数,函数返回的就是它们的最小公倍数。这里调用了之前写好的gcd()函数来计算每个数与前面所有数的最大公因数。注意,相乘的时候要使用整除运算符//,否则可能会产生浮点数误差。