问题描述
所以，我的问题是找到从1到20均匀分配到所有数字的最小倍数。我确实成功地解决了这个任务，但我的程序运行得相当慢。 这是代码，ni使用的最终数字是1亿。 你可以想象，这需要很多时间。 所以我想知道，我将如何优化此代码？ 另外，知道如何改变它应该分成的数字是很好的，所以不是1到20，而是说1到15。
function smallestMultiple(n) {
for (i = 0; i< n; i++) {
if (i%1 === 0 && i%2 === 0 && i%3 === 0 && i%4 === 0 && i%5 === 0
&& i%6 === 0 && i%7 === 0 && i%8 === 0 && i%9 === 0
&& i%10 === 0 && i%11 === 0 && i%12 === 0 && i%13 === 0
&& i%14 === 0 && i%15 === 0 && i%16 === 0 && i%17 === 0
&& i%18 === 0 && i%19 === 0 && i%20 === 0 ) {
console.log(i);
}
};
};
现在，显然，这需要5分钟才能找到答案。 我想知道是否有更有效的方法？ 编辑：显然我也可以使用1-20的变量。 如果您有答案，请仔细解释您的答案以及为什么它更有效率。
1楼
Justin Koenig
6
2015-07-31 00:00:51
我想我发现了一个最优雅的解决方案，直接来自论坛：
在没有真正尝试的情况下，我想这里的一些“蛮力”方法违反了“1分钟规则”。 但是，考虑到微小的改变可以大大提高算法的效率。
假设“强力”方法是：迭代每个自然数 - 如果当前数字可以被1到20中的每个数字整除，你就找到了答案。
考虑一下：如果你知道N的解是X，那么N + 1的解必须可以被X整除。因此，当迭代自然数时，你可以迭代X而不是1.而不是检查数字1到N + 1的可分性，你只需要检查N + 1，因为你已经知道值（X的倍数）都可以被1到N整除。
作为一个例子，假设10的答案是2520，为了得到11的解，我们检查2520是否可被11整除。不是，我们迭代到5040并检查它是否可被11整除。我们继续直到我们发现27720可以被11整除，这就是答案。
尽管没有尝试直接确定LCD，但这最终成为一种相当快速的算法，在较小的N值下，在一秒钟内容易运行。
在Ruby中（虽然类似的方法可以在许多高级语言中使用）：
def snd（max）result = 1 for n in 1..max prev = result while result％n> 0 result + = prev end end return result end
放snd（20）
然后我将其解释为Javascript并获得此脚本
console.log("Please type in smallestMultiple(n), whereas n is the smallest multiple."); function smallestMultiple(n) { var result = 1; var prev; for (i=1; i<n+1; i++) { prev = result; while (result%i > 0) { result += prev; } } console.log(result); };
<script src="https://getfirebug.com/firebug-lite-debug.js"></script>
编辑：在脚本中发现一个错误，返回smallestNumber(11) = 2520.在for循环中修复：for（i = 0; i < n + 1 ; i ++）
2楼
dave
3
2015-07-30 23:45:13
使用的方法
跳过数字1 - 10，因为您可以将它们中的任何一个乘以2并获得列表中的另一个因子。
function GCF(a, b) {
if (b == 0) return a;
else return (GCF (b, a % b));
}
function LCM(a, b) {
return Math.abs(a*b) / GCF(a, b);
}
LCM(11, LCM(12, LCM(13, LCM(14, LCM(15, LCM(16, LCM(17, LCM(18, LCM(19, 20)))))))));
为任意n做，不是超级优化，但它很简单：
function LCM_N(n) {
var x = 1;
while (n > 1) {
x = LCM(n, x);
n--;
}
return x;
}
3楼
PitaJ
0
2015-07-30 23:45:28
那么，你想要1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20的最小公倍数
这与20,19,18,17,16,15,14,13,12,11的最小公倍数（LCM）相同，因为1,2,3,4,5,6,7,8,9 ，10是其他十个数字的所有因素。
你应该使用while循环，因为它们更快。
最小公倍数必须小于或等于20,19,18,17,16,15,14,13,12,11的倍数，因此n可以等于此开始。
i可以按序列中所有素数的倍数开始：19 * 17 * 13 * 11 * 7 * 5 * 3 * 2
break循环。
这可能是你花了这么长时间的原因。
我们可以增加20，因为它是答案之间可能的最小差异。
function lowestCommonMultipleof20Through1(){
var i = 19*17*13*11*7*5*4*3;
var n = 20*19*18*17*16*15*14*13*12*11;
while(i < n){
if( i%11 === 0 &&
i%12 === 0 &&
i%13 === 0 &&
i%14 === 0 &&
i%15 === 0 &&
i%16 === 0 &&
i%17 === 0 &&
i%18 === 0 &&
i%19 === 0 &&
i%20 === 0 ){
console.log(i);
break;
}
i+=20;
}
}
我几乎立刻就得到了232792560。