最大公约数的几种基本求解方法

给定两个数a,b,若a>b，求解他们的最大公约数

方法1.试除法:由于最大公约数r满足1

代码实现:

方法2.辗转相除法: 1.若a%b=0，显然，b为最大公约数。2.若a%b!=0，则令a=b,b=a%b,接着a%b，若a%b=0,则此时的b为最大公约数，否则令继续令a=b，b=a%b……如此循环往复，直到a%b=0,b为最大公约数。 即-若f(a,b)为a，b的最大公约数，a%b!=0且b%(a%b)!=0,则有f(a,b)=f(b,a%b)。

代码实现:

但是如果a

方法3.更相减损术:1.判断它们是否都是偶数。若是，则用2约简,计数约简次数n；若不是则执行第二步。2.若a>b，则a-b=c，此时若b=c，则b*(

代码实现:

补充：求解最小公倍数-若给定数字a，b ，其最大公约数为p，最小公倍数为q，有a*b=p*q。因此只需求解最大公约数，则可得最小公倍数

文章知识点与官方知识档案匹配，可进一步学习相关知识C技能树首页概览115589 人正在系统学习中