初三网全国地区

请选择

    返回
    初三网 > 初中数学 > 数学知识点 > 正文

    最大公约数怎么求算法

    文/刘鑫

    求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。如果有一个自然数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的最大公约数。

    相关阅读

    16与24的最大公约数

    2021-02-03

    最大公约数和最小公倍数的关系

    2020-05-15

    孔乙己人物形象特点分析 讲述了什么故事

    2022-10-19

    自然界产生氧气的化学方程式 光色素种类有哪些

    2022-10-19

    综合评价招生报考条件 有哪些优势

    2022-10-19

    中括号在数学中的含义 括号的作用是什么

    2022-10-19

    济南最好的职高学校 济南职高学校推荐

    2022-10-19

    应然和实然是什么意思 两者有区别吗

    2022-10-19

    地理地中海气候特点 地中海气候主要分布在哪里

    2022-10-19

    碱石灰的主要成分是什么

    2022-10-19

    济阳职业中等专业学校地址在哪里 怎么去

    2022-10-19

    亟需和急需的区别是什么

    2022-10-19

    综合评价招生是什么意思 报名条件是什么

    2022-10-19

    怎样提高英语写作能力 英语作文万能句子

    2022-10-19

    可见光波长范围是多少 有哪些特性

    2022-10-19