JavaScript-项目Euler#5-效率 [英] JavaScript - Project Euler #5 -- efficiency

问题描述

这是针对Euler项目的问题5.

This is for Project Euler, problem #5.

任务是找到可被数字1-20整除的最小数字.我的代码似乎可以在1-18上运行，但是从19开始，我的浏览器开始超时.这使我相信我的代码效率低下.

The task is to find the smallest number evenly divisible by numbers 1-20. My code seems to work on 1-18, but at 19 my browser starts timing out. This leads me to believe my code is just inefficient.

如何缓解这种情况?

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)

推荐答案

另一种具有蛮力和余数模分类的选项

another option with brute force and modulo rest-classification

这个问题可以通过简单的通用模余数特性来解决. 查看从1到20的数字并将其分为两组，并在它们之间找到一些独特的共有属性.

this problem can be solved with a simple common modulo rest class characteristics. look at the numbers from 1 to 20 and divide it into two groups and find some unique common attributes between them.

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

   we are building a division with the same reminder members

1全部除掉

2除以4,8->> 8重要

2 divide 4,8 -->>8 important

3除以6,9，而6不除以9-> 6,9

3 divide 6,9 but 6 doesnt divide 9 evenly--> 6,9

5分10->> 10重要

5 divide 10-->> 10 important

剩下6,7,8,9,10来检查是否有1中的任何数字可以将其除以余数0.

that leaves us with 6,7,8,9,10 to check if there is any number from 1 that can divide this with rest 0.

诀窍是，如果2,4,8除以相同的提示而设的数字为16，那么我们就不必检查2,4除以16，我们只需检查8.

the trick is if 2,4,8 divides a number let say 16 with the same reminder then we don't have to check if 2,4 divides 16, we check only 8.

11 12 13 14 15 16 17 18 19 20

11 12 13 14 15 16 17 18 19 20

在这里，我们可以从大约数字的上方进行大约同样的操作，而我们将剩下的

here we can do the same from about with factors of the numbers from above and we will be left with

11 12 13 14 15 16 17 18 19 20

11 12 13 14 15 16 17 18 19 20

注意:我们知道必须除数的最后一个数字是20， 因此，这意味着解决方案将是一个以0结尾的数字，或者是 20的因子之一，因此我们建立20的因子，并检查11 12 13 14 15 16 17 18 19可以将其分割，然后完成.

NB: we know that the last number that has to divide the number is 20, so that means either the solution will be a number ending with 0 or is one of the factors of 20, so we build factors of 20 and check if 11 12 13 14 15 16 17 18 19 can divide it then we are done.

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)

相同的想法也适用于我为进行第一个推论而做出的类似推论 问题似乎较小.

The same idea applies analogue to the first deduction I made to make the problem seems smaller.

//最小数字可被1到10的所有数字整除

//smallest number divisible by all numbers from 1 to 10

int a = 10;

    while (a % 6 != 0 || a % 7 != 0 | a % 8 != 0 || a % 9 != 0 )
    {
        a += 10;
    }

console.log(a)

//最小数字可被1到5的所有数字整除

//smallest number divisible by all numbers from 1 to 5

int i = 5;                          

    while (i % 3 != 0 || i % 4 != 0)
    {
        i += 5;
    }

console.log(i)

这篇关于JavaScript-项目Euler#5-效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！