辗转相除法解决最大公约数，最小公倍数等于两数之积除以其最大公约数 （C语言代码）

解题思路: 辗转相除法解决最大公约数，最小公倍数等于两数之积除以其最大公约数

注意事项:

算法原理：若a除以b的余数为r , 则有 (a , b) = ( b ,r )  （(a,b)表示a和b的最大公约数）

例：169与48的最大公约数求解过程

169 = 48 * 3 + 25    —— (169 , 48) = (48 , 25)

48 = 25 * 1 + 13 ——(48 , 25) = (25 , 13)

25 = 13 * 1 + 12

13 = 12 * 1 + 1

12 = 1 * 12  + 0 ——(12 , 1 ) = 1 

故最大公约数为 1  

参考代码:

//输入两个正整数m和n，求其最大公约数和最小公倍数。

#include <stdio.h>

void File(int m,int n)//最大公约数

{

         int r;

         r=m%n;  

while(r)

{

         m=n;

         n=r;

         r=m%n;

}

printf("%d ",n);

}

void Fl(int m,int n)//最小公倍数

{

     int r,sum;

     sum=m*n;

     r=m%n;

while(r)

{

         m=n;

         n=r;

         r=m%n;

}

sum=sum/n;

printf("%d",sum);

}

int main()

{

     int m,n;

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

     File(m,n);

     Fl(m,n);

}