欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个正整数a ,b 的最大公约数。
定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 最大公约数(greatest common divisor)缩写为gcd 。
辗转相除法的结果条件是两个数取模等于零,即一个数能整除另外一个数时,此时较小的数就是最大公约数
算法思想:(最小公倍数=两个整数之积/最大公约数)
(1) 对于已知两数m,n, 使得m>n;
(2) m 除以n 得余数r ;
(3) 若r=0,则n 为求得的最大公约数, 算法结束;否则执行(4);
(4) m←n,n←r,再重复执行(2).
方法举例理解
1、 查找约数法.先分别找出每个数的所有约数,再从两个数的约数中找出公有的约数,其
中最大的一个就是最大公约数.例如,求12和30的最大公约数. 12的约数有:1、2、3、4、6、12; 30的约数有:1、2、3、5、6、10、15、30. 12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数.
2、 辗转相除法.当两个数都较大时,采用辗转相除法比较方便.其方法是:以小数除大数,
如果能整除,那么小数就是所求的最大公约数.否则就用余数来除刚才的除数;再用这新除法的余数去除刚才的余数.依此类推,直到一个除法能够整除,这时作为除数的数就是所求的最大公约数.例如:求4453和5767的最大公约数时,可作如下除法. 5767÷4453=1余1314 4453÷1314=3余511 1314÷511=2余292 511÷292=1余219 292÷219=1余73 219÷73=3 于是得知,5767和4453的最大公约数是73.
则对于题目中所给按算法思想求出32和24的最大公约数,可按照上面方法进行计算。
32÷24=1 余 8 24÷8=3 于是得知,32和24的最大公约数是8.