Skip to content

Latest commit

 

History

History
105 lines (78 loc) · 3.75 KB

gcd.md

File metadata and controls

105 lines (78 loc) · 3.75 KB
Raw
标题 标签
gcd(最大公约数) math,recursion,intermediate(数学，递归，两者之间)

计算两个或多个数字之间的最大公约数。

  • 使用递归。
  • 使用 array_reduce() 和 gcd 函数将 y 应用于 $numbers 列表中的所有元素。
  • 基本情况是 y 等于 0。在这种情况下，返回 x。
  • 否则，返回 y 的 gcd 和除法 x/y 的余数。

特别解释

最大公约数（Greatest Common Divisor, GCD），又称 最大公因数（Greatest Common Factor, GCF），是指能够同时整除两个或多个整数的最大整数。换句话说，最大公约数是这两个数的所有公约数中最大的一个。

计算最大公约数的方法

  1. 辗转相除法（欧几里得算法）
    这是计算两个数最大公约数的经典方法，基于以下定理：

    • 对于两个整数 ( a ) 和 ( b )（假设 ( a > b )），它们的最大公约数等于 ( a ) 除以 ( b ) 的余数和 ( b ) 的最大公约数，即： [ \text{GCD}(a, b) = \text{GCD}(b, a \mod b) ]
    • 这个过程会重复进行，直到余数为 0，此时较小的数即为最大公约数。

    步骤：

    1. 计算 ( a \div b ) 的余数 ( r )。
    2. 将 ( a ) 替换为 ( b )，将 ( b ) 替换为余数 ( r )。
    3. 重复上述步骤，直到余数为 0，此时的 ( b ) 即为最大公约数。

    示例：
    计算 ( \text{GCD}(48, 18) )：

    • ( 48 \div 18 = 2 ) 余数 ( 12 )；
    • ( 18 \div 12 = 1 ) 余数 ( 6 )；
    • ( 12 \div 6 = 2 ) 余数 ( 0 )；
    • 余数为 0 时，最大公约数为 6。

  2. 列举法
    列举法是指将两个数的所有公约数列举出来，选择其中最大的一个。例如：

    • 对于 ( 48 ) 和 ( 18 )，可以列举出它们的约数：
      • ( 48 ) 的约数：1, 2, 3, 4, 6, 8, 12, 16, 24, 48
      • ( 18 ) 的约数：1, 2, 3, 6, 9, 18
      • 公约数：1, 2, 3, 6
      • 最大公约数是 6。

  3. 质因数分解法
    质因数分解法是将每个数分解为质因数的乘积，然后取公共的质因数的最低次幂。

    示例：

    • ( 48 = 2^4 \times 3 )
    • ( 18 = 2 \times 3^2 )
    • 公共的质因数是 2 和 3，取它们的最低次幂：
      • ( 2^1 \times 3^1 = 6 )
    • 所以，( \text{GCD}(48, 18) = 6 )。

Python 中计算最大公约数

Python 提供了内置的函数 math.gcd() 来计算两个数的最大公约数。你只需要传入两个整数即可。

import math

a = 48
b = 18

gcd = math.gcd(a, b)
print(f"最大公约数是: {gcd}")

最小公倍数与最大公约数的关系

最大公约数和最小公倍数是两个相关的概念。对于两个数 ( a ) 和 ( b )，它们的 最小公倍数（LCM） 和 最大公约数（GCD） 满足以下关系：

[ \text{LCM}(a, b) \times \text{GCD}(a, b) = a \times b ]

这个公式意味着，如果你知道两个数的最大公约数，你可以计算出它们的最小公倍数，反之亦然。

总结

  • 最大公约数（GCD） 是两个数的所有公约数中最大的一个。
  • 常见的计算方法有 辗转相除法、列举法 和 质因数分解法。
  • 在 Python 中，可以使用 math.gcd() 来快速计算最大公约数。

ps: 根据上述，这里采用了第一种方法，辗转相除法，也即欧几里得算法来计算。

代码如下:

function gcd(...$num){
    if(count($num) > 2){
        return array_reduce($num,'gcd');
    }
    $r = $num[0] % $num[1];
    return $r === 0 ? abs($num[1]) : gcd($num[1],$r);
}

使用方式:

gcd(8, 36); // 4
gcd(12, 8, 32); // 4