辗转相除法求两个数的最大公约数和最小公倍数
输入两个数a,b, 求其最大公约数和最小公倍数
注意：设最大公约数和最小公倍数分别为m,n，辗转相法能直接求出最大公约数，却不能直接求出最小公倍数，n=a*b/m。
辗转相除法：
r1=a%b
如果r1=0,则除数b为最大公约数；
r2=b%r1
如果r2=0,则除数r1为最大公约数；
r3=r1%r2
如果r3=0,则除数r3为最大公约数......
找到令余数r为0的除数即为最大公约数。
最小公倍数n即为n=a*b/m。
求最小公倍数代码：
#include <stdio.h>
int main()
{
int a,b,t,r,f;
while(scanf("%d%d",&a,&b)!=EOF)
{
if(a<b)
{
t=a;
a=b;
b=t;
}
f=a*b;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
printf("%d
",f/a);
}
return 0;
}
补充：用递归形式求最大公约数
int gcd(int a, int b)
{
if(b == 0) return a;
else
return gcd(b, a%b);
}
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
如何在Git Hub上学习开源项目+社交