求两个数的最大公约数和最小公倍数的算法

如题所述

分别把两个数做质因数分解,
把相同质因数跳出来,取两者较小的次幂乘起来,就是最大公约数
两个数的积除以最大公约数,就是最小公倍数
比如说12和40
12=2^2*3
40=2^3*5
最大公约数=2^2=4
最小公倍数=12*40/4=120
温馨提示:内容为网友见解,仅供参考
第1个回答  2019-10-10
分解质因数的方法,例:30和40,30=2*3*5,40=2*2*2*5,所有公有质因数的乘积是这两个数的最大公因数,公有的乘各自特有是这两个数的最小公倍数,30和40公有1个2和1个5,所以最大公因数是2*5=10。30还特有公因数1个3,40还特有2个2,最小公倍数是2*5*3*2*2=120
第2个回答  2019-10-13
最大公约数求两个数列如:2和3最大公约数是6,两数相乘,最小公倍数列如:8和4最小公倍数是2,两数相除
用短除法求最大公约数,如果两个数是质数,最小公倍数则是他们的乘积,否则是短除法所有的数的乘积
第3个回答  2019-10-15
最大公约数,例如36和96,36=2*2*3*3,96=2*2*2*2*2*3,最大公约数为2*2*3=12
最大公倍数显然36约数中比96多一个3,所以96*3=288就是他们的最大公倍数
希望你看懂了