辗转相除法求最大公倍数和最小公因数_辗转相除法求最大公因数

辗转相除法求最大公倍数和最小公因数

一、辗转相除法的基本思路

求两个数的最大公倍数和最小公因数
思路：假设两个数分别为a与b
1.求出a除以b的余数 也就是 t = m%n
2.将除数的值赋给被除数 也就是 m = n
3.将余数的值赋给除数 也就是 n = t

将以上三步循环执行 直到除数n = 0
此时被除数a的值就是这两个数的最大公因数
而最大公因数的值则为 这两个数的乘积除以最大公因数

二、使用代码

int main()
{
    int a, b;
    cin >> a >> b;

    int m = a;
    int n = b;

    while (n)
    {
        int t = m % n;
        m = n;
        n = t;
    }

    cout << "最大公因数为：" << m << endl;
    cout << "最小公倍数为：" << a * b / m << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20