当前位置:首页 > 时尚生活

求最大公约数 最大公约数求法大全

小评论

上次我们介绍了一种求最大公约数的特殊方法,叫做除法。你还记得吗?

欧几里得算法

将较大的数除以较小的数,然后将除数除以出现的余数(第一个余数),然后将第一个余数除以出现的余数(第二个余数),并重复此操作,直到最后一个余数为0。如果要求两个数的最大公约数,那么最终的除数就是这两个数的最大公约数。

所以,今天我们就来总结一下求最大公约数的方法。

求最大公约数方法综述

1.素因子分解方法

思维:将每个数分解成素因子,然后提取每个数中所有的公共素因子相乘,得到的乘积就是这些数的最大公约数。

例如,假设我们找到24和60的最大公约数。

第一步:分解24和60。

24=2X2X2X3

60=2X3X2X5

第二步:24和60的最大公约数= 24和60共享的公因数相乘,即2X2X3=12。

2.短除法

思考:用短除法求最大公约数,首先连续去掉这些数的公约数,直到所有商数互为素数,然后将所有除数相乘,得到的乘积就是这些数的最大公约数。

短除法的本质是素因子分解法,但素因子分解是用短除法符号进行的。

示例:

12的因子是:1,2,3,4,6,12。

18的因子是:1,2,3,6,9,18。

12和18的公因数是:1,2,3,6。

12和18之间最大的公因数是6。

3、多相损耗法

思考:

第一步:任意给两个正整数;确定是否都是偶数。如果是,用2减;如果没有,执行第二步。

第二步:将较小的数减去较大的数,然后将差值与较小的数进行比较,再将该数减去较大的数。继续此操作,直到产生的减数和差值相等。

那么第一步中的一些2和第二步中的相等数的乘积就是最大公约数。

示例:

用多失相法求98和63的最大公约数。

因为63不是偶数,所以将98和63减一个大的数并减去它们:

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以98和63的最大公约数等于7。

代码实现:

4.转身分开

捻转除法和除法在前一篇文章中有详细介绍。

欧几里得算法

你掌握了多少种方法~

1.《求最大公约数 最大公约数求法大全》援引自互联网,旨在传递更多网络信息知识,仅代表作者本人观点,与本网站无关,侵删请联系页脚下方联系方式。

2.《求最大公约数 最大公约数求法大全》仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证。

3.文章转载时请保留本站内容来源地址,https://www.lu-xu.com/shehui/648231.html

上一篇

陈进平 陈进平:巧手扎出板凳龙

下一篇

武大分数线 武汉大学2020年录取分数线出炉,全国一卷湖北录取分数线最低

二年级乘除法口算题100道 一年级的孩子一分钟口算多少题才算能达标?

二年级乘除法口算题100道 一年级的孩子一分钟口算多少题才算能达标?

有些学校要求3分钟100题。很多父母和孩子都觉得有点痛苦新学期过半,一个小学一年级的家长在网上发帖,对学校要求的口算很不满意:“我真的不明白,才一年级,三分钟算100题有什么意义?”帖子引起很多家...

最大公约数是什么意思 互质数是什么意思 判断方法有哪些

最大公约数是什么意思 互质数是什么意思 判断方法有哪些

互质数为数学中的一种概念,即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数,叫做互质数。什么是互质数公因数只有1的两个非零自然数,叫做互质数。互质数具有以下定理:(1)两个...

二年级除法题300道 谁能帮忙出300道二年级下期的数学竖式题

题目:谁能帮忙出300道二年级下期的数学竖式题解答:25 -15 -80 = 10 -80 = -70 26 -6 -64 = 20 -64 = -44 27 + 3 -48 = 30 -48 =...

最大公约数怎么求算法 设计一个求两个数的最大公约数的通用函数,算法不限,要求能反复输入数据并输出其最大公约数.

题目:设计一个求两个数的最大公约数的通用函数,算法不限,要求能反复输入数据并输出其最大公约数.解答:#include /* 最大公约数 */int GreatestCommonDivisor (...

用短除法求最大公因数 3个数怎么用短除法求最大公因数和最小公倍数

题目:3个数怎么用短除法求最大公因数和最小公倍数假如要求4,6,8的最小公倍数,用短除法,那么用2约以后是2,3,4,我想问一下2和4还能用2约吗?是不是求最小公倍数要约,有点搞混了,解答:求3个...

四年级四则运算500道 四年级小数脱式计算题(加减乘除法)要500道!

题目:四年级小数脱式计算题(加减乘除法)要500道!不要简便的!加减乘除都要!要脱式解答:2.1÷7÷0.1=5×2.1+2.1=2.5×4×0.5=50×0.04+420=3.4÷0.1-21=...

辗转相除 C语言程序填空:用辗转相除法求两个整数的最大公约数 帮帮

题目:C语言程序填空:用辗转相除法求两个整数的最大公约数 帮帮 #includevoid main(){int a,b,r;int *p1,*p2;p1=&a;p2=&b;printf("inpu...

除法分配律公式 除法有分配律吗

除法分配律公式 除法有分配律吗

没有除法分配律,只有乘法分配律。乘法分配律是指两个数的和与一个数相乘,可以先把它们分别与这个数相乘,再相加。被除数连续除以两个除数,等于除以这两个除数之积。除法运算性质被除数扩大(缩小)n倍,除数...