【欧几里得算法】求解最大公约数和最小公倍数

解题思路:

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

求最小公倍数可以用最大公因数和最小公倍数之间的性质：两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。
注意事项:

注意判断循环前和循环中两个数大小，顺序

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    int array[2],array1[2],temp;

    for (int a = 0; a <= 1; a++) {

        cin >> array[a];

    }

    if (array[0] < array[1]) {

        sort(array, array + 1);

        temp = array[0];

        array[0] = array[1];

        array[1] = temp;

        array1[0] = array[0];

        array1[1] = array[1];

        for (; array[1] != 0;) {

            int a = (array[0] / array[1]);

            array[1] = (array[0] % array[1]);

            array[0] = (array[0] - array[1]) / a;

            a = 0;

            sort(array, array + 1);

        }

        cout << array[0] << " " << (array1[0] * array1[1]) / array[0];

    }

    else {

        array1[0] = array[0];

        array1[1] = array[1];

        for (; array[1] != 0;) {

            int a = (array[0] / array[1]);

            array[1] = (array[0] % array[1]);

            array[0] = (array[0] - array[1]) / a;

            a = 0;

            sort(array, array + 1);

        }

        cout << array[0] << " " << (array1[0] * array1[1]) / array[0];

    }

}