JavaScript -项目Euler #5 --效率
这是针对Project Euler的问题#5。
任务是找到能被数字1-20整除的最小数字。我的代码似乎可以在1-18上运行，但是在19号时，我的浏览器开始超时。这让我相信我的代码是低效的。
我如何缓解这种情况？
function divisible(a){
counter = 0;
result = 2;
while (counter < a){
for (var x = 0; x <= a; x ++){
if (result % x === 0){
counter ++;
}
}
if (counter != a){
counter = 0;
result ++;
}
}
return result;
}
divisible(20)回答 3
Stack Overflow用户
发布于 2015-10-02 08:54:11
基本上，您需要的是1，...,20的least common multiple。
我将使用gcd实现lcm，这可以使用fast Euclidean algorithm来实现。
function gcd(a, b) {
return b === 0 ? a : gcd(b, a%b); // Euclidean algorithm
}
function lcm(a, b) {
return a * b / gcd(a, b);
}
function divisible(a){
var result = 1;
for(var i=2; i<=a; ++i)
result = lcm(result, i);
return result;
}
divisible(20); // 232792560Stack Overflow用户
发布于 2015-10-02 08:34:17
是啊，效率很低。您需要更改算法。我能想到的最有效的方法是分解2到20之间的所有数字(使用因子和计数:例如，18是3*3* 2，或者对于最终的{ 3: 2, 2: 1 }是两次3和一次2)；然后找到每个因子的最大值，并将它们相乘。
一个简短的例子:可以被18和16整除的最小数字：
18: { 3: 2, 2: 1 }
16: { 2: 4 }
maximums of factor repetitions: { 3: 2, 2: 4 }
result: 3^2 * 2^4 = 144将数字从2分解到20很容易；如果你不知道如何做到这一点，有很多可能的算法，你可以在the Wikipedia article on integer factorisation上找到想法。
Stack Overflow用户
发布于 2016-10-19 13:15:29
具有蛮力和模REST分类的另一种选择
这个问题可以用一个简单通用的模REST类特征来解决。查看从1到20的数字，并将其分成两组，找出它们之间的一些独特的共同属性。
%1%2%3%4%5%6%7%8%9 10
we are building a division with the same reminder members1除以所有
2除4,8 -->8重要
3除6,9，但6不等分9--> 6,9
5分10-->> 10重要
这就给我们留下了6,7,8,9,10来检查是否有从1开始的任何数字可以除以剩余的0。
诀窍是，如果2,4,8除以一个数字，比如16，同样的提示，那么我们不必检查2,4是否除以16，我们只需要检查8。
11 12 13 14 15 16 17 18 19 20
在这里，我们可以对上面数字的因子做同样的事情，我们将得到
11 12 13 14 15 16 17 18 19 20
NB:我们知道必须除以这个数字的最后一个数字是20，这意味着要么解决方案将是一个以0结尾的数字，要么是20的一个因子，所以我们建立20的因子，并检查11 12 13 14 15 16 17 18 19是否可以除以它，然后我们就完成了。
int start = 20;
while (start % 11 != 0 || start % 12 != 0 | start % 13 != 0 || start % 14 != 0 ||
start % 15 != 0 || start % 16 != 0 || start % 17 != 0 || start % 18 != 0 || start % 19 != 0 )
{
start += 20;
}
console.log(start)，同样的想法也适用于我的第一个推论，以使问题看起来更小。
//可被1到10之间的所有数整除的最小数
int a = 10;
while (a % 6 != 0 || a % 7 != 0 | a % 8 != 0 || a % 9 != 0 )
{
a += 10;
}
console.log(a)//可被1到5之间的所有数整除的最小数
int i = 5;
while (i % 3 != 0 || i % 4 != 0)
{
i += 5;
}
console.log(i)https://stackoverflow.com/questions/32898775
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号