求最大公约数——欧几里得算法

时间:2022-02-03 12:51:15

欧几里得算法的原理:基于这样一种观察,两个整数x和y(x>y)的最大公约数等同于y和(x%y)的最大公约数;

数t整除x和y,当且仅当t整数y和(x%y);这是因为:x = t*y + x%y;

具体代码如下:

#include <iostream>
#include <stdlib.h>

using namespace std;

int gcd(int x, int y)
{
    cout << x << " " << y << endl;
    if (0 == y)
    {
        return x;
    }
    return gcd(y, x%y);
}

int main(int argc, char *argv[])
{
    int x = atoi(argv[1]);
    int y = atoi(argv[2]);

    cout << gcd(x, y) << endl;

    return 0;
}