求两个数的最大公约数

Question

我想找到两个输入数字之间的最大公约数，但我遇到了一个问题。

我不确定我用来求除数的方法是否正确。我通过将这两个数字除以每个数字，直到该数字达到自身来做到这一点。

#include <iostream>
#include <string>

using namespace std;
    
int main() {

    int num1, num2;
    int large = 0;
    int gcd = 0;

    cout << "this program finds the greatest common divisor" << endl;
    cout << "input first  number > "; cin >> num1; 
    cout << "input second number > "; cin >> num2;

    if (num1 > num2)
        large = num1;
    else
        large = num2;

    cout << "larger number  > " << large << endl;
    cout << endl;

    for (int i = 0; i < large + 1; i++) {
        if (num1 % i == 0 && num2 % i == 0) {
            gcd = i;
        }
    }

    cout << "The gcd of " << num1 << " and " << num2 << " is " << gcd << endl;
    cout << endl;
}

Answer 1

是的，这是有道理的。 基本上它可以完成工作。你做了一些不必要的事情。开始循环：

for (int i = 0; i < large + 1; i++)

当 i=1 时，因为你不能除以 0。当 i 介于较大和较小的数字之间时，你还会执行不必要的模运算。 Ofc可以优化很多。显然，对于更小/2 到更小的数字，您也找不到公约数（不包括边界数字），并且比之前的更小/3 到更小/2（-#-）。然而逻辑似乎很可靠：循环中最后找到的除数将是最大公约数。

Answer 2

您需要进行一些修改才能使其正确。
首先检查其中一个是否为零，如果是，则返回另一个。
其次，如果这没有发生，则开始从 1（而不是零）开始除以最小的（而不是最大的）。

int gcd, small;
if (num1 == 0)
    gcd = num2;
else if (num2 == 0)
    gcd = num1;
else
{
    if (num1 < num2)
        small = num1;
    else
        small = num2;
    for (gcd = 1; gcd < small + 1; gcd++)
        if (num1 % gcd == 0 && num2 % gcd == 0)
            break;
}
cout << "The gcd of " << num1 << " and " << num2 << " is " << gcd << endl;

但是你现在应该知道有更简单、更快的方法，比如我对这个问题的回答。

Answer 3

#包括

使用命名空间 std；

int main() {

int num_1 = 25;
cout << "input any number = \n";
cin >> num_1;
int num_2 = 15;
cout << "input any number = \n";
cin >> num_2;
int sum = 0;

    for (int i = 1; i <= num_1 && i<=num_2; i++) {
        if (num_1 % i == 0 && num_2 % i == 0) {
            sum = i;
        }
    }
    cout << sum << endl;
    
return 0;

}