GCD(最大公约数)和LCM(最小公倍数)的求法

时间:2022-06-03 04:03:54

GCD(最大公约数)

(1)辗转相除法(欧几里得算法)(常用)

  将两个数a, b相除,如果余数c不等于0,就把b的值给a,c的值给b,直到c等于0,此时最大公约数就是b

(2)更相减损术

  将两个书中较大的数a减去较小的数b,如果差c等于0,那么最大公约数为b,如果不等于0,则将b的值给a,c的值给b,继续相减知道差等于0

LCM(最小公倍数)

  假设x和y的最大公约数是m,最小公倍数是n,则x*y = m*n