用辗转相除法求19351和3661的最大公约数和最小公倍数.
问题描述：
用辗转相除法求19351和3661的最大公约数和最小公倍数.
答
#include
int gcd(int a,int b)
{
while(a>b?(a=a%b):(b=b%a));
return a+b;
}
int main()
{
int a,b;
int i ,j;
while(scanf("%d%d",&a,&b)!=EOF)
{
printf("%d\n",gcd(a,b));
printf("%d\n",a*b/gcd(a,b));
}
return 0;
}
523
135457
答
1
答
19351除以3661= 商5 余数 1046
3661除以1046 =商3余数 523
1046除以523= 商 2余数 0
最大公约数=523
最小公倍数=19351×3661/523=135457