20240112公约数与公倍数

代码

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm(x, y):
    return x * y // gcd(x, y)

num1 =12 
num2=18
print(gcd(num1,num2))   # 6
print(lcm(num1,num2))   #36

概念

公约数
在数学中，两个或多个整数的公约数是能够整除它们的正整数。换句话说，一个数的公约数是能够同时整除这个数和另一个数的数。例如，考虑数字18和24，它们的公约数包括：

1. 1：因为1可以整除任何数。
2. 2：因为18和24都可以被2整除。
3. 3：因为18可以被3整除。
4. 6：因为18和24都可以被6整除。

因此，1、2、3和6都是18和24的公约数。公约数中最大的一个称为最大公约数（GCD，Greatest Common Divisor）。

如果两个或多个数的最大公约数是1，这些数被称为互质数。互质数是指它们之间没有共同因数（除了1）。例如，5和7是互质数，因为它们的最大公约数是1。

公倍数
在数学中，两个或多个整数的公倍数是能够同时整除这些整数的最小正整数。换句话说，一个数的公倍数是能够同时整除这个数和其他数的数。

考虑两个整数 a 和 b，它们的公倍数包括：

1. 0：因为0可以整除任何数。
2. a：因为 a 能整除 a。
3. b：因为 b 能整除 b。
4. a * b：因为 a * b 能整除 a 和 b。
5. 2 * a：因为 2 * a 能整除 a。
6. 2 * b：因为 2 * b 能整除 b。

以此类推，所有能够同时整除 a 和 b 的整数都是它们的公倍数。而其中最小的正整数是它们的最小公倍数（LCM，Least Common Multiple）。

例如，考虑整数4和6。它们的公倍数包括 0、4、6、8、12、16、18 等，而它们的最小公倍数是12。因为12是能够同时整除4和6的最小正整数。

代码功能

gcd- 计算两个数的最大公约数

lcm-计算两个数的最小公倍数

代码解释

gcd的循环

1. 条件： 循环的条件是 while y，即当 y 不等于0时，继续执行循环。
2. 循环体： 在每一轮循环中，执行 x, y = y, x % y，这是一个元组解包操作。这一步是欧几里德算法的关键。它将 x 更新为原来的 y，同时将 y 更新为 x 除以 y 的余数。
3. 重复： 循环会一直执行，直到 y 的值为0。当 y 为0时，循环结束，此时 x 的值即为最大公约数。

欧几里德算法的核心思想是反复用较小的数取代较大的数，直到较大的数变为0。最终，非零的较小数就是最大公约数。这个算法在每一步都通过取余操作实现，同时不断更新两个数的值。这样的处理方式更加高效，因为它避免了直接的除法操作。

lcm公倍数的计算

两个整数 x 和 y 的乘积等于它们的最大公约数与最小公倍数的积。所以，通过这个关系，可以用最大公约数来计算最小公倍数。