php实现欧几里得算法实现

欧几里得算法简介

欧几里得算法（辗转相除法）用于计算两个非负整数的最大公约数（GCD）。其核心思想是：
gcd(a, b) = gcd(b, a % b)，直到余数为0时，此时的除数即为最大公约数。

PHP实现方法

方法1：迭代实现

通过循环逐步计算余数，直到余数为0：

function gcd($a, $b) {
    while ($b != 0) {
        $temp = $a % $b;
        $a = $b;
        $b = $temp;
    }
    return $a;
}
// 示例调用
echo gcd(48, 18); // 输出：6

方法2：递归实现

利用递归简化代码逻辑：

function gcd($a, $b) {
    return ($b == 0) ? $a : gcd($b, $a % $b);
}
// 示例调用
echo gcd(56, 98); // 输出：14

边界条件处理

• 负数处理：通过取绝对值确保输入为非负数。

  function gcd($a, $b) {
    $a = abs($a);
    $b = abs($b);
    return ($b == 0) ? $a : gcd($b, $a % $b);
  }

• 零值处理：若其中一个数为0，直接返回另一个数。

  function gcd($a, $b) {
    if ($a == 0) return $b;
    if ($b == 0) return $a;
    return gcd($b, $a % $b);
  }

性能优化

• 大数优化：PHP的整数范围受系统位数限制（如32位系统中最大为2^31-1），超出时需使用gmp扩展：

  function gmp_gcd($a, $b) {
    return gmp_strval(gmp_gcd($a, $b));
  }
  // 示例调用（需安装GMP扩展）
  echo gmp_gcd('12345678901234567890', '9876543210'); // 输出：90

应用场景

• 分数化简：计算分子分母的最大公约数。
• 密码学：RSA算法中密钥生成步骤涉及GCD计算。

通过上述方法，可灵活应对不同需求的欧几里得算法实现。