求两个整数的公因数和最大公因数是数学计算中的基础问题，在分页计算、数据分组、比例缩放等业务场景中经常会遇到。PHP作为一门通用脚本语言，虽然没有内置的最大公因数函数（PHP 7之前），但用几行代码就能实现高效的求解算法。本文将详细讲解辗转相除法的原理与实现，以及如何枚举出两个整数的全部公因数。
辗转相除法的原理与PHP实现
辗转相除法又称欧几里得算法，是求解最大公因数最经典的方法。它的核心思想基于一个数学定理：两个整数a和b（a大于b）的最大公因数，等于b与a除以b所得余数的最大公因数。也就是说，gcd(a, b) = gcd(b, a mod b)，当余数为0时，除数就是最大公因数。
举个例子，求48和36的最大公因数：48除以36余12，问题转化为求36和12的最大公因数；36除以12余0，此时12就是答案。整个过程只需要两步迭代，比逐个枚举效率高得多。这个算法的时间复杂度是对数级别的，即使两个数非常大，迭代次数也很有限。
用PHP实现可以采用循环或递归两种写法。循环写法如下：
<?php
function gcd(int $a, int $b): int {
// 确保处理非负数
$a = abs($a);
$b = abs($b);
while ($b != 0) {
$temp = $b;
$b = $a % $b;
$a = $temp;
}
return $a;
}
echo gcd(48, 36); // 输出 12
?>递归版本代码更简洁，数学表达更直接：
<?php
function gcdRecursive(int $a, int $b): int {
if ($b == 0) {
return abs($a);
}
return gcdRecursive($b, $a % $b);
}
echo gcdRecursive(1071, 462); // 输出 21
?>递归写法虽然优雅，但如果两个数之间存在特殊关系导致迭代次数极多，可能会消耗较多调用栈。PHP的递归深度本身有默认限制，对于一般业务场景两种写法都可以放心使用，追求稳妥可以优先选择循环版本。
枚举法求两个整数的所有公因数
如果业务需要的不只是最大公因数，而是所有公因数的列表，可以采用枚举法。思路是遍历从1到两数中较小值的每一个整数，判断它是否能同时整除两个数，能整除的就是公因数。最大公因数自然就是结果集合中的最大值。
枚举法的实现非常直观：
<?php
function commonDivisors(int $a, int $b): array {
$a = abs($a);
$b = abs($b);
$result = [];
$limit = min($a, $b);
for ($i = 1; $i <= $limit; $i++) {
if ($a % $i == 0 && $b % $i == 0) {
$result[] = $i;
}
}
return $result;
}
$divisors = commonDivisors(48, 36);
print_r($divisors); // 输出 1, 2, 3, 4, 6, 12
echo max($divisors); // 输出 12，即最大公因数
?>枚举法的时间复杂度是O(min(a, b))，当两个数达到千万级别时，循环耗时就会明显增加。有一种优化手段可以显著减少遍历次数：只遍历到较小值的平方根，每找到一个因数i，就同时得到配对因数limit除以i，再判断这个配对因数是否也是另一个数的因数即可。这样能把遍历范围从线性降到平方根级别。
另外还有一种更巧妙的方式：先求出最大公因数g，然后枚举g的所有因数，这些因数就是两数的全部公因数。因为公因数必然是最大公因数的因数，这个性质可以大幅缩小枚举范围，特别适合两数很大但最大公因数较小的情况。
更相减损术与PHP内置函数方案
除了辗转相除法，中国古代数学中的更相减损术也能求最大公因数。它的原理是：两个不相等的数，用较大的数减去较小的数，得到的差与较小的数继续比较相减，直到两数相等，这个相等的数就是最大公因数。这种方法只用减法和比较运算，避免取模运算，在某些没有取模指令的环境中反而更快。
<?php
function gcdSubtract(int $a, int $b): int {
$a = abs($a);
$b = abs($b);
while ($a != $b) {
if ($a > $b) {
$a = $a - $b;
} else {
$b = $b - $a;
}
}
return $a;
}
echo gcdSubtract(98, 63); // 输出 7
?>需要注意的是，当两数差距悬殊时，比如求1000000和1的最大公因数，更相减损术要减很多次才能收敛，性能远不如辗转相除法。实际工程中可以结合两者优点，即Stein算法，用位移代替除法，不过对于PHP这种脚本语言来说，通常没必要做到这么极致。
如果项目使用PHP 7.2及以上版本，并且安装了GMP扩展，可以直接使用内置函数gmp_gcd，它是C语言实现的大整数最大公因数计算，性能和精度都最有保障：
<?php
$result = gmp_gcd("123456789012345", "987654321098765");
echo gmp_strval($result); // 输出大整数的最大公因数
?>综合来看，普通的中小整数用自实现的辗转相除法即可满足需求，涉及超大整数或高并发计算时建议启用GMP扩展。求全部公因数时，优先采用先算最大公因数再枚举其因数的策略，能把性能开销控制在最低水平。掌握这几种方法的原理和适用边界，遇到任何公因数相关的需求都能从容应对。