最大公约数和最小公倍数

发表于 | 分类于 |

最近脑子突然冒出一个有趣的想法，怎么求最大公约数和最小公倍数。看来网上的一些算法，下面算是自己的一些理解吧。

  1. 辗转相除法：就是用小数除大数，如果余数不是零，就把余数和较小的数构成一组新数，继续上面的除法，知道大数被小数约尽，此时比较小的数就是最大公约数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    var maxCommon = function (a, b) {
    	var c = a % b;
    	while (c != 0) {
    		a = b;
    		b = c;
    		c = a % b;
    	}
    	return b;
    };

  2. 更相减损法：用大数减去小数，将差和较小的数构成一对新数，再用大数减去小数 一直到差与较小数相等 此时差就是最大公约数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    var maxCommon = function (a, b) {
    	while (a != b) {
    		var m = Math.min(a, b);
    		var n = Math.abs(a - b);
    		return maxCommon(m, n); //要加return，返回给上一层
    	}
    	return a;
    };
    //或
    var maxCommon = function (a, b) {
    	if (a != b) {
    		var m = Math.min(a, b);
    		var n = Math.abs(a - b);
    		return maxCommon(m, n); //这里也要加return，返回给上一层
    	} else {
    		return a;
    	}
    };

    以上加 return 的原因应该是，对于有返回值的函数的递归调用一定要记得加 return

  3. 穷举法，遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    var maxCommon = function (a, b) {
    	var c;
    	if (a < b) {
    		c = a;
    		a = b;
    		b = c;
    	}
    	for (var i = 1; i <= b; i++) {
    		if (a % i == 0 && b % i == 0) {
    			c = i;
    		}
    	}
    	return c;
    };

    当然还有其他算法，有兴趣的朋友可以可以自己去研究下。

    既然我们都取到了公约数，那公倍数就是在是太简单了。将两个数相乘除以最大公约数即可。

    1
    2
    3
    4
    5
    var minCommon = function (a, b) {
    	var c = maxCommon(a, b);
    	var d = (a * b) / c;
    	return d;
    };

[越努力，越幸运！]