题目:

找出能被两个给定参数和它们之间的连续数字整除的最小公倍数。

范围是两个数字构成的数组,两个数字不一定按数字顺序排序。

例如对 1 和 3 —— 找出能被 1 和 3 和它们之间所有数字整除的最小公倍数。

思路:

这里涉及到经典算法:求最大公约数gcd(greatest common divisor)和最小公倍数scm(smallest common multiple)
gcd(最大公约数)算法过程(欧几里德算法/辗转相除法)
有两整数a和b:
① a%b得余数c,即c=a%b
② 若c=0,则b即为两数的最大公约数
③ 若c≠0,则a=b,b=c,再回去执行①

scm算法(最小公倍数算法)
最小公倍数=两整数的乘积÷最大公约数,即scm=(a*b)/gcd(a,b)

代码:

<script type="text/javascript">
	function smallestCommons(arr) {
		arr = arr.sort(function(a, b) {
			return a - b;
		});
		console.log(arr);
		//递归求最大公约数
		function gcd(a, b) {
			if (a % b === 0) {
				return b;
			} else {
				return gcd(b, a % b);
			}
		}
		//a,b的最小公倍数=a*b/(a和b的最大公约数)
		var val = arr[0];
		for (var i = arr[0] + 1; i <= arr[1]; i++) {
			// console.log('val='+val+' i='+i);
			// console.log('他们的最大公约数是:'+gcd(val,i));
			val = val * i / gcd(val, i);
			// console.log('求公倍数后 val='+val+' i='+i);

		}
		return val;

	}
</script>

 

———————
作者:kimihiro_41
原文:https://blog.csdn.net/kimihiro_41/article/details/73740067