辗转相除法又名欧几里德算法，是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

———来源：搜狗百科

核心思路

求最大公约数方法：辗转相除法

求最小公约数方法：(num1 x num2)÷最大公约数

例：求125 15 两数的最大公约数和最小公倍数。

解：125 / 15 = 8 ······· 5

15 / 5 = 3 ······· 0

所以两数的最大公约数为5，最小公倍数为 (125 x 15) ÷ 5 = 375

C语言代码

#include <stdio.h>

int main() {
    int a, b, n1, n2, t; // 声明a b n1 n2 t 
    printf("请输入两位数：\n");
    scanf("%d %d", &a, &b); // 用户输入a b
    n1 = a; // 赋值
    n2 = b; // 赋制 
    //辗转相除开始 
    while (n2) {
        t = n1 % n2;
        n1 = n2;
        n2 = t;
    }
    //辗转相除结束 
    //输出结果 
    printf("最大公约数 %d\n", n1);
    printf("最小公倍数是 %d\n", a * b / n1);
    return 0;
}

运行编译上述代码，输入125 15，将会得到以下结果：

请输入两位数：
125 15
最大公约数 5
最小公倍数是 375