首页 > 8 其它知识 > 最大公约数和最小公倍数知识

最大公约数和最小公倍数知识

2010年11月27日 AEROFISH 3,085 views 发表评论 阅读评论

最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf),指某几个整数共有因子中最大的一个。
最小公倍数(Least Common Multiple,缩写lcm),指某几个整数公共倍数中最小的一个。

几个数学概念:

约数、倍数:如果数A能被数B整除(B不为零),A就叫做B的倍数,B就叫做A的约数(或因数、因子),倍数和约数是相互依存的。

公约数:几个数公有的约数叫做这几个数的公约数。一个数的约数的个数是有限的,其中最小的是1,最大的是它本身。例: 在2、4、6中,2就是2,4,6的最大公约数。

公倍数:几个数公有的倍数叫做这几个数的公倍数,其中最小的一个,叫做这几个数的最小公倍数。一个数的倍数是无限的,几个数的公倍数也是无限的。

质数:也称素数,指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。如:2、3、5、7、11……

质约数:也称质因数、质因子,既是约数又是质数的数。

分解质因数:一个大自然数,可以分解为多个质因数的相乘。方法从最小的质数开始分解。例如:12=2×6=2×2×3。

求最大公约数gcd:

欧几里得的辗转相除法:gcd(a,b)=gcd(b, a mod b),其中"a mod b"是指"a ÷ b"的余数。该方法是在求两个较大数的gcd时,可以等效为求两个较小数的gcd,通过反复多次mod后,余数为零时,则最小的数(非零)即为gcd。
例如,求123456和7890的最大公约数:

a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

最后最小的数为6,即123456和7890的最大公约数为6。

求最小公倍数lcm:

方法一:利用分解质因数的方法可以求出两个数的最小公倍数。
两个数一个称为大数,另一个称为小数,对两个数分别分解质因数,然后保留大数的所有质因数,再乘上小数中不重复的质因数,所得的积就为最小公倍数。
例1:求6和8的最小公倍数。
 6=2×3,8=2×2×2,
 保留8中的2×2×2,再乘上6中的3(2为重复的),
 所以6和8的最小公倍数是:(2×2×2)×3=24 。
例2:求12和8的最小公倍数。
 12=2×2×3,8=2×2×2,
 其中重复的为2×2,
 所以12和8的最小公倍数是:(2×2×3)×2=24。

方法二:先求gcd再求lcm。
最小公倍数等于两数之积除以最大公约数。
例:求12和8的最小公倍数。
 12和8的最大公约数为4,
 12×8÷4=24 ,
 所以两数的最小公倍数是24。


本文对我无帮助,减1分本文对我有帮助,加1分(本文对您有帮助吗?目前总+1分,1参与者。)
Loading ... Loading ...

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.