我如何找到带有while循环的GCD？模运算符如何工作？

Question

#include <iostream>

int GCD()
{
    int a,b,k;
    cout<<"Enter a and b"<<endl;
    cin>>a>>b;
    cout<<endl;

    if (a>b)
    {
        k=a;
    }
    else
    {
        k=b;
    }

    cout<<k<<endl;

    do
    {
        k=k-1;
    } while(a%k !=0 && b%k !=0);

    cout<<k<<endl;

    return 0;
 }

为什么这样的程序无法正常工作？例如，当我输入125且5时答案是25，但应该是5？ while循环中的逻辑有问题吗？据我了解，问题在于模运算符。当k击中25时，表示125%25=0和5%=25=0。我该如何解决？

Answer 1

您在这里有一些错误：

1. GCD小于或等于

   lower数字。当前，您开始使用较大的数字进行检查。您需要将if块翻转到if (a<b)。 （不完全是一个错误，但是您检查的数字超出了所需的数量）

2. 您需要检查初始k是否为GCD。使用do {} while()时，您要检查的第一个数字是k-1。请改用简单的while。同样，循环条件也存在逻辑缺陷。

while (!((a % k == 0) && (b % k == 0)))
{
    k--;
}

请注意，模数周围的括号不是必需的，但是会稍微提高可读性。
您的代码将不会在所有编译器中编译，并且您不应忽略名称空间std::。

Answer 2

您的while语句有逻辑错误。必须是

while(!(a%k == 0 && b%k == 0));

[当k等于25时，125%25==0因此，在您的while语句中，a%k !=0部分等于false，因此它退出您的do-while，但需要测试b%k是否等于0或不！
[此外，当a和b大时，您的实现往往会执行缓慢。您可以看一下solutions。