<?php
/**
 * 问题：求两个自然数的最大公约数。
 *
 * 分析：这个是基础的数学问题，最大公约数指两个数字公共的约数中最大的，例如数字6的约数有1、2、3、6，数字9的约数有1、3、9，则数字6和数字9的公共约数有1和3，其中3是最大的公约数。
 *
 * 第四种思路：另一种方法是采用中国国人发明的更相减损法，更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
 * 步骤：
 * 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
 * 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
 * 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
 * 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。
 * 比如：用更相减损术求260和104的最大公约数。由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
 * 此时65是奇数而26不是奇数，故把65和26辗转相减：
 * 65-26=39
 * 39-26=13
 * 26-13=13
 * 所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52
 */

$a = 44;
$b = 88;
$c = gcd($a, $b);
var_dump($c);

/**
 * 求两个自然数的最大公约数(更相减损法)
 * 避免了取模运算，但是算法性能不稳定，最坏时间复杂度为O(max(a, b)))
 * @param int $a
 * @param int $b
 * @return mixed
 */
function gcd($a, $b)
{
    if (!is_numeric($a) || !is_numeric($b)) {
        return false;
    }

    if ($a === $b) {
        return $a;
    }

    $min = $a > $b ? $b : $a;
    $max = $a > $b ? $a : $b;

    return gcd($max - $min, $min);

}