java - 欧几里得算法不正确的结果

Question

我正在尝试编写 Euclid 算法的 Java 实现:我的方法主体如下所示:

    while(a%b != 0) {
        int newA = b * ((int) Math.floor(a/b));
        int newB = a - newA;

        a = newA;
        b = newB;
    }
    return a;

但是，我不断得到不正确的结果......我想我有一个逻辑错误，但真的不明白它在哪里:\

有什么想法吗？

Answer 1

欧几里得算法如下:

1. 如果 a < b, swap(a, b);
2. [a, b] = [b, a % b], 直到 a % b == 0;
3. 返回 b.

您的代码有多个问题，但比较突出的一个是您返回的是a，而不是b。

另一件事:不要试图重新发明 %(余数)运算符。