PHP 查找两个数字的最大公约数GCD

 PHP 常用例子

GCD 代表最大公约数。两个数的 GCD 是能整除这两个数的最大数。

例如 - 20 和 25 的 GCD 是 5，50 和 100 的 GCD 是 50。

方法1:使用For循环求两个数字的GCD

在下面的例子中，for循环用于将变量i从0迭代到较小的数字。如果两个数字都可以被 i 整除，则它会修改 GCD，并最终给出两个数字的 GCD。

<?php
$x = 50;
$y = 100;

if ($x > $y) {
  $temp = $x;
  $x = $y;
  $y = $temp;
}

for($i = 1; $i < ($x+1); $i++) {
  if ($x%$i == 0 and $y%$i == 0)
    $gcd = $i;
}

echo "GCD of $x and $y is: $gcd";
?> 

上面的代码将给出以下输出:

GCD of 50 and 100 is: 50 

方法2:使用While循环求两个数的GCD

在下面的例子中，较大的数被替换为一个大数减去较小数的数数字。继续该过程，直到两个数字相等，这将是两个数字的 GCD。

<?php
$p = $x = 20;
$q = $y = 25;

while ($x != $y) {
  if ($x > $y)
    $x = $x - $y;
  else
    $y = $y - $x;
}

echo "GCD of $p and $q is: $x";
?> 

上面的代码将给出以下输出:

GCD of 20 and 25 is: 5 

方法3:使用递归函数求两个数字的GCD

In下面的例子，使用了递归函数。在此方法中，不使用减法运算符（如上例所示），而是使用模运算符。此方法也称为欧几里得算法。

<?php
function gcd($x, $y) {
  if ($y == 0)
    return $x;
  return gcd($y, $x%$y);
}

$x = 250;
$y = 475;

echo "GCD of $x and $y is: ".gcd($x,$y);
?> 

上面的代码将给出以下输出:

GCD of 250 and 475 is: 25