全国

    当前位置:

  • 热门地区:
  • 选择地区:
  • ×
当前位置: 初三网 > 初中数学 > 数学知识点 > 正文

最大公约数怎么求算法

2020-11-06 17:27:03文/刘鑫

求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。

最大公约数怎么求算法

辗转相除法

使用到的原理很聪明也很简单,假设用f(x,y)表示x,y的最大公约数,取k=x/y,b=x%y,则x=ky+b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x,y)=f(y,x%y)(y>0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。

例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数。

查看更多【数学知识点】内容