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

时间:2022-11-24 08:51:02

要求最小公倍数可先求出最大公约数

设要求两个数a,b的最大公约数

伪代码:

int yushu,a,b;

while(b不等于0)

{

yushu=a对b求余

b的值赋给a

yushu的值赋给b

}

代码:

  

int gongyue()
{
int yushu,a,b;
while(b)
{
yushu=a%b;
a=b;
b=yushu;
}
return b;
}

  此子函数可以求出两个数的最大公约数n    最小公倍数为a*b/n;