- 辗转相除法：两个正整数a和b（a > b）, 它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
function getGreatestCommonDivisor(a, b) {
let big = Math.max(a, b),
small = Math.min(a, b);
if(big % small === 0) {
return small;
}
return getGreatestCommonDivisor(big % small, small)
}
- 更相减损术：两个正整数a和b（a > b）, 它们的最大公约数等于a-b的差值c和较小数b之间的最大公约数。
function getGreatestCommonDivisor2(a, b) {
if(a === b) {
return a;
}
let big = Math.max(a, b),
small = Math.min(a, b);
return getGreatestCommonDivisor(big - small, small);
}
网友评论