超级无敌简单易懂的最大公约数与最小公倍数解答

解题思路:

     辗转相除法又称为欧几里德算法。这个方法大家已经都已经在数学上学过了。具体的步骤就是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。最后的除数就是这两个数的最大公约数。举个例子就是：比如两个数字，x=453，y=36；

453%36=21；

36%21=15；

21%15=6；

15%6=3；

6%3=0；

%是取余符号，大家应该都知道吧。所以用这个算法可以求出453和36的最大公约数是3；

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

//辗转相除

int f(int n, int m)

{

    if(m%n==0)return n;

    else f(m, n%m);

}

int main()

{

    int n, m;

    scanf("%d%d",&n, &m);

    printf("%d %d\n", f(n, m), n*m/f(n, m));

    return 0;

}