以下都是我个人的理解,
如果有哪里不对的地方还请赐教(

记住一个公式是 $$ a = b \cdot q + r $$
其中ab就是要被求GCD的两个数字。

举个例子,比如我要求gcd(90,65),则得出: $$ 90 = 65 \cdot q + r $$
那么经过计算式子1,得到 $ q = 1 $ ,$ r = 15 $,即 $ 90 = 65 \cdot 1 + 15 $。
接下来,把 $ 90 = 65 \cdot 1 + 15 $ 中的 b 赋值予 ar 赋值予 b ,再塞回那个公式里,得到 $$ 65 = 15 \cdot q + r $$
继续计算,得到 $ q = 4 $ , $r = 5 $。即 $65 = 15 \cdot 4 + 5 $ 。
然后不断重复上述步骤,一直到 $r = 0$ 。
当 $r = 0$ 时,它上一条的r就是这个两个数的最大公约数了。

比如这样
gcd(90,65)


一个php的实现:

<?php

function gcd($a, $b) {
    calculate: $r = $a % $b;
    if ($r <> 0) {
        $a = $b;
        $b = $r;
        goto calculate;
    }
    else if ($r == 0) {
        return $b;
    }
}

标签: none