public static int getCM(int m, int n) {
int max = m > n ? m : n;
int min = m + n - max;
// 欧几里得算法(辗转相除法)
while (min != 0) {
int temp = min;
min = max % min;
max = temp;
}
return (m * n) / max;
}
欧几里得算法:
设两个正整数为a和b,并且a > b。那么a和b的最大公约数等于b和a % b的最大公约数。
换句话说,如果我们将a除以b得到的余数记为r,那么a和b的最大公约数等同于b和r的最大公约数。这个过程可以一直重复下去,直到余数为零时停止。此时,非零的那个数就是最大公约数。

京公网安备 11010502036488号