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

辗转相除法（又名欧几里德法），C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：

gcd(a,b) =a(b=0)
gcd(a,b)=gcd(b,a mod b)(b!=0)

其算法过程为：（前提）设两数为a、b，其中a 做被除数,b做除数，temp为余数

1. 大数放a中、小数放b中；
2. 求a/b的余数；
3. 若temp=0，则b为最大公约数；
4. 如果temp!=0则把b的值给a,temp的值给b；
5. 返回第2步。

算法实现

#include<stdio.h>
int divisor (int a,int b)    //求两数的最大公约数
{
int  temp;          //定义整型变量
if(a<b)             //通过比较求出两个数中的最大值和最小值
    { temp=a;a=b;b=temp;} //设置中间变量进行两数交换
while(b!=0)           //通过循环求两数的余数，直到余数为0
    {
        temp=a%b;
        a=b;              //变量数值交换
        b=temp;
    }
return (a);            //返回最大公约数到调用函数处
}
int multiple (int a,int b)  //求两数的最小公倍数
{
int divisor (int a,int b); //调用divisor();
int temp;
    temp=divisor(a,b);  //再次调用divisor()函数，求出最大公约数
return  (a*b/temp); //返回最小公倍数到主调函数处进行输出
}
int main()  
{
int m,n,t1,t2;     //定义整型变量
printf("please input two integer number:"); //提示输入两个整数
scanf("%d%d",&m,&n);              //通过终端输入两个数
    t1=divisor(m,n);                  
    t2=multiple(m,n);                 
printf("The highest common divisor is %d\n",t1);  //输出最大公约数
printf("The lowest common multiple is %d\n", t2);  //输出最小公倍数
return 0;
}