有关C语言-辗转相除法

辗转相除法
辗转相除法是求最大公约数的一种算法,是由古希腊著名数学家欧几里得在公元前300年左右提出的,因而又叫欧几里得算法.这个算法本质上揭示了一个定理: 对于两个正整数a>b,如果a=bq+r(0<r≤b),那么a,b的最大公约数等于b,r的最大公约数.
其算法的具体步骤为:
第一步:输入两个正整数a,b(a>b),
第二步:计算a÷b的余数r;
第三步:a=b,b=r;
第四步:若r=0,则最大公约数为n;否则返回第二步

——————————————————————–
除数变被除数,余数变除数,直到没有余数(除尽为止)return 最后的除数

先求出最大公约数,然后最小公倍数为a*b/最大公约数

[cce]
/*
辗转相除法求整数m,n最大公约数
*/
int gcd(int m,int n)
{
int t;
while(t=m%n)
{
m=n;
n=t;
}
return n;
}

/*求最小公倍数*/
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
[/cce]

发表评论

电子邮件地址不会被公开。 必填项已用*标注