使用欧几里德算法求 GCF(GCD)

Question

我正在尝试编写一个函数来查找 2 个数字的 gcd，使用我发现的欧几里德算法 here。

From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number. (or without getting a negative answer) Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCF is the next-to-last small number result. Also see our Euclid's Algorithm Calculator.
Example: Find the GCF (18, 27)
27 - 18 = 9
18 - 9 = 9
9 - 9 = 0
So, the greatest common factor of 18 and 27 is 9, the smallest result we had before we reached 0.

按照这些说明，我编写了一个函数：

int hcf(int a, int b)
{
    int small = (a < b)? a : b;
    int big = (a > b)? a : b;
    int res;
    int gcf;

    cout << "small = " << small << "\n";
    cout << "big = " << big << "\n";

    while ((res = big - small) > small && res > 0) {
            cout << "res = " << res << "\n"; 
    }
    while ((gcf = small - res) > 0) {
        cout << "gcf = " << gcf << "\n";
    }


    return gcf;
}

然而，第二个循环似乎是无限的。谁能解释一下为什么？

我知道该网站实际上显示了代码(PHP)，但我正在尝试仅使用他们提供的说明来编写此代码。

Answer 1

当然这个循环是无限的：

while ((gcf = small - res) > 0) {
    cout << "gcf = " << gcf << "\n";
}

small 和 res 在循环中不会改变，所以 gcf 也不会。该循环等效于：

gcf = small - res;
while (gcf > 0) {
    cout << "gcf = " << gcf << "\n";
}

这可能更清楚。

我会将该算法移植到代码如下：

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        }
        else {
            b -= a;
        }
    }
    return a;
}

虽然通常 gcd 是使用 mod 实现的，因为它要快得多：

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}

使用欧几里德算法求 GCF(GCD)

Using Euclid Algorithm to find GCF(GCD)

c++

algorithm

greatest-common-divisor