Python 中两个数字的 GCD|极客教程

Python 中两个数字的 GCD

1. 什么是 GCD？

GCD，全称为 Greatest Common Divisor，即最大公约数。在数学上，给定两个或多个整数，它们的最大公约数是能够整除所有这些整数的最大正整数。最大公约数常用缩写为 GCD。

例如，给定两个整数 8 和 12，它们的最大公约数是 4。

2. 如何计算两个数字的 GCD？

在 Python 中，计算两个数字的 GCD 可以使用 built-in 函数 math.gcd()。该函数可以在 math 模块中找到。

下面是使用 math.gcd() 函数计算两个数字的 GCD 的示例代码：

import math

# 定义两个数字
num1 = 8
num2 = 12

# 使用 math.gcd() 计算 GCD
gcd = math.gcd(num1, num2)

# 输出结果
print("The GCD of", num1, "and", num2, "is", gcd)

运行结果：

The GCD of 8 and 12 is 4

3. 用辗转相除法计算 GCD

除了使用 math.gcd() 函数之外，我们还可以使用辗转相除法（Euclidean algorithm）来计算两个数字的 GCD。

辗转相除法是一种用于计算两个非负整数的最大公约数的简单而有效的方法。该算法基于以下原理：如果 a 能够整除 b，那么 a 和 b 的最大公约数就是 b；否则，a 和 b 的最大公约数就是 b 与 b 除以 a 的余数之间的最大公约数。

下面是使用辗转相除法计算两个数字的 GCD 的示例代码：

# 定义辗转相除法函数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 定义两个数字
num1 = 8
num2 = 12

# 使用辗转相除法计算 GCD
gcd_value = gcd(num1, num2)

# 输出结果
print("The GCD of", num1, "and", num2, "is", gcd_value)

运行结果：

The GCD of 8 and 12 is 4

4. 使用辗转相除法计算 GCD 的原理

下面我们来详细解释一下辗转相除法计算 GCD 的原理。

假设我们有两个非负整数 a 和 b，其中 a 大于等于 b。首先，我们计算 a 除以 b 的余数 r。如果 r 等于 0，则 b 就是 a 和 b 的最大公约数；如果 r 不等于 0，则我们继续计算 b 除以 r 的余数 r1。我们继续这个过程，直到余数等于 0。最后一个非零余数就是 a 和 b 的最大公约数。

例如，假设我们要计算 8 和 12 的最大公约数。首先，我们计算 12 除以 8 的余数，得到 4。接着，我们计算 8 除以 4 的余数，同样得到 4。由于 4 不等于 0，我们继续计算 4 除以 4 的余数，得到 0。由于余数等于 0，所以 4 就是 8 和 12 的最大公约数。

5. 使用 GCD 求解实际问题

最大公约数在计算机科学中有着广泛的应用，下面是几个实际问题，在解决这些问题时可能会用到 GCD。

5.1 简化分数

假设我们有一个分数，如 8/12，我们可以使用 GCD 来简化这个分数。

我们可以将分子（8）和分母（12）都除以它们的最大公约数，来得到一个等价的分数。

下面是使用 GCD 简化一个分数的示例代码：

import math

# 定义一个分数
numerator = 8
denominator = 12

# 计算分子和分母的最大公约数
gcd_value = math.gcd(numerator, denominator)

# 简化分数
simplified_numerator = numerator // gcd_value
simplified_denominator = denominator // gcd_value

# 输出结果
print("The simplified fraction is", simplified_numerator, "/", simplified_denominator)

运行结果：

The simplified fraction is 2 / 3

5.2 构建最简分数的列表

假设我们要找出某个给定范围内的所有最简分数，并将它们保存到一个列表中。

下面是使用 GCD 构建最简分数的列表的示例代码：

import math

# 定义函数用于构建最简分数的列表
def build_simplified_fraction_list(start, end):
    fraction_list = []
    for numerator in range(start, end + 1):
        for denominator in range(start, end + 1):
            gcd_value = math.gcd(numerator, denominator)
            simplified_numerator = numerator // gcd_value
            simplified_denominator = denominator // gcd_value
            fraction_list.append((simplified_numerator, simplified_denominator))
    return fraction_list

# 构建最简分数的列表
start_range = 1
end_range = 5
fraction_list = build_simplified_fraction_list(start_range, end_range)

# 输出结果
print("List of simplified fractions:")
for fraction in fraction_list:
    print(fraction[0], "/", fraction[1])

运行结果：

List of simplified fractions:
1 / 1
1 / 2
2 / 1
1 / 3
2 / 3
3 / 1
1 / 4
3 / 4
4 / 1
1 / 5
2 / 5
3 / 5
4 / 5
5 / 1

6. 结论

在 Python 中，我们可以使用 math.gcd() 函数或辗转相除法来计算两个数字的最大公约数（GCD）。GCD 在解决一些实际问题时非常有用，如简化分数和构建最简分数的列表等。掌握如何计算 GCD 可以让我们更加高效地解决这些问题。

Python 中两个数字的 GCD