Euler #5工程效率和误差
该网站提出的问题：
2520是最小的数，可以除以从1到10的每一个数，没有任何余数。
什么是最小的正数，可以被从1到20的所有数字整除？
我的问题
我遇到了一个问题，涉及到代码中的效率和错误。当我无法通过我的方式时，我一直在研究和寻找其他的答案，但我仍然不明白这是如何实现的。而且，当我用1-10插入2520时，我的代码显然不起作用。
--请注意，我做了而不是想要关于效率的答案或解决方案，只是对我如何实现它的一个解释(AKA是一个提示)。但是对于我的代码中的错误，我想要一个解决方案。提前感谢您的帮助！
var recentArray = [];
var fullArray = [];
var numberCheck = 20;
function makeNewNumbers(i1, i2) {
for (var i = i1; i < i2; i++) {
recentArray = [];
for (var j = 2; j <= numberCheck; j++) {
recentArray.push(i % j);
}
fullArray.push(recentArray);
}
}
var counter = 0;
var iStart = 0,
iLess = 1000;
var success = false;
var newCheck = setInterval(function () {
while (counter < 10 && success === false) {
counter++;
makeNewNumbers(iStart, iLess);
for (var o = 1; o < fullArray.length; o++) {
recentFound = false;
if (numberCheck === 20 && fullArray[o][0] === 0 && fullArray[o][1] === 0 && fullArray[o][2] === 0 && fullArray[o][3] === 0 && fullArray[o][4] === 0 && fullArray[o][5] === 0 && fullArray[o][6] === 0 && fullArray[o][7] === 0 && fullArray[o][8] === 0 && fullArray[o][9] === 0 && fullArray[o][10] === 0 && fullArray[o][11] === 0 && fullArray[o][12] === 0 && fullArray[o][13] === 0 && fullArray[o][14] === 0 && fullArray[o][15] === 0 && fullArray[o][16] === 0 && fullArray[o][17] === 0 && fullArray[o][18] === 0) {
clearInterval(newCheck);
console.log("Success!!! Number: " + o);
success = true;
break;
} else if (numberCheck === 10 && fullArray[o][0] === 0 && fullArray[o][1] === 0 && fullArray[o][2] === 0 && fullArray[o][3] === 0 && fullArray[o][4] === 0 && fullArray[o][5] === 0 && fullArray[o][6] === 0 && fullArray[o][7] === 0 && fullArray[o][8] === 0) {
clearInterval(newCheck);
console.log("Success!!! Number: " + o);
success = true;
break;
}
}
}
iStart += 1000;
iLess += 1000;
console.log("Not found...\nSearch is continued. To postpone type \'clearInterval(newCheck)\'\nNerd stats: --- Starting minimum: " + iStart + " --- Starting maximum: " + iLess);
}, 1);回答 3
Stack Overflow用户
发布于 2015-11-13 22:23:38
有两个bug是上面的算法：
内部counter循环不会增加iStart和iLess。因此，第二次迭代给出了具有零1000th i的数组元素。这就是为什么它给出了答案1000。应该在该循环中增加iStart和iLess：
while (counter < 10 && success === false) {
// ...
iStart += 1000;
iLess += 1000;
}变量counter在整个循环运行后不会重置为零。因此，最大探测数是9999。在while循环之后，counter应该设置为零。
这种算法效率很低。它能够解决10的问题。可能它可以用于15。但是，我不希望在合理的时间内收到20的结果。
在给定范围内计算所有数的素数因子(1..20)可以得到更有效、更明显的算法。对于范围内的所有数字，每个唯一素数的最大计数应该被乘以来给出结果。使用欧几里德算法可以做得更好。
Stack Overflow用户
发布于 2015-11-13 22:29:08
当处理像这样的问题时，要简化它，而不需要失去问题的本质。它将更容易完成。例如，解决这个更简单的问题：
12是最小的数，可以除以从1到4的每一个数，没有任何余数。
先用钢笔、纸和伪码完成，必要时再进行编码。
还检查在使用%RE余物运算符时是否没有余数，并保持运行计数。您似乎在将结果存储在一个不必要的数组中。
还有另一个提示--你要求我们不评论效率，但它在问题的标题中。
由于这是一个欧拉问题，即使是一个蛮力算法，增加20和检查其他数字依次是如此之快，欧几里德方法的知识是不必要的。它只需要一个答案，而不是一个有效的方法。
对于较大的数字，效率要求和“数字溢出”检查都需要考虑。
Stack Overflow用户
发布于 2015-11-13 22:39:16
用数学，而不是蛮力。
什么是最小的正数，可以被从1到20的所有数字整除？
从数学上讲，这被称为1，…，20的最小公倍数。
计算两个数字的最小公共倍数的一个非常快速的方法是使用欧氏算法来计算最大公约数。
function gcd(a, b) { // Greatest common divisor
if(b == 0) return a;
return gcd(b, a%b);
}
function lcm(a, b) { // Least common multiple
return a * b / gcd(a, b);
}
var n = 1;
for(var i=1; i<=20; ++i) n = lcm(n, i);
n; // 232792560https://stackoverflow.com/questions/33702110
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号