求几个数的最大公因数的三种方法
怎么找最大公因数?
怎么找最大公因数?
求公因数和最大公因数是针对两个数或两个数以上来说。根据数的特征。先找出能整除这几个数公有的质因数开始除起。一般从最小的质数开始。如果是求两个数这两个数的商,除到互质数为止。
求三个数的最大,公因数与最小公倍数过程有所不同。最大公因数只包含这几个数,公有的质因数连乘起来。
最小公倍数,既含有公有的质因数,还包括各自独有的质因数连乘起来。
算两个自然数最大公因数的公式?
最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。
质因数分解法:就是把一个合数分解成几个质数相乘的形式。
48和54
482*2*2*2*3
542*3*3*3
因此,48和54的最大公约数是:2*36.
短除法是求最大公因数的一种方法,也可用来求最小公倍数。求几个数最大公因数的方法,开始时用观察比较的方法,即:先把每个数的因数找出来,然后再找出公因数,最后在公因数中找出最大公因数.
辗转相除法是用来求最大公约数的.给出两个正整数a和b,用b除a得商a0,余数r,写成式子 aa0b r,0≤rb.
(1) 这是最基本的式子,辗转相除法的灵魂.如果r等于0,那么b可以除尽a,而a、b的最大公约数就是b. 如果r≠0,再用r除b,得商a1,余数r1,即 ba1r r1,0≤r1r.
(2) 如果r10,那么r除尽b,由(1)也除尽a,所以r是a、b的公约数.反之,任何一除尽b的数,由(1),也除尽r,因此r是a、b的最大公约数. 如果r1≠0,则用r1除r得商a2,余数r2,即 ra2r1 r2,0≤r2r1.
(3) 如果r20,那么由(2)可知r1是b、r的公约数,由(1),r1也是a、b的公约数.反之,如果一数除得尽a、b,那末由(1),它一定也除得尽b、r,由(2),它一定除得尽r、r1,所以r1是a、b的最大公约数. 如果r2≠0,再用r2除r1,如法进行.由于brr1r2…逐步小下来,而又都是正整数,因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1).这就是有名的辗转相除法,在外国称为欧几里得算法.