CODEWITHSUNDEEP
javascriptmath
Bairdley
Bairdley

Reputation: 21

JavaScript - Project Euler #5 -- efficiency

This is for Project Euler, problem #5.

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.

How can I mitigate this?

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)

Upvotes: 2

Views: 391

Answers (3)

Seek Addo
Seek Addo

Reputation: 1893

another option with brute force and modulo rest-classification

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

   we are building a division with the same reminder members

1 divides all

2 divide 4,8 -->>8 important

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

5 divide 10-->> 10 important

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.

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

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

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.

//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)

//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)

Upvotes: 1

Oriol
Oriol

Reputation: 288300

Basically, you want the least common multiple of 1,...,20.

I would implement lcm by using gcd, which can be implemented using the 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); // 232792560

Upvotes: 2

Amadan
Amadan

Reputation: 198388

Yup, inefficient. You would need to change the algorithm. The most efficient I can think of is to factorise all the numbers from 2 to 20 (with factors and counts: e.g. 18 is 3 * 3 * 2, or twice 3 and once 2, for final { 3: 2, 2: 1 }); then find the maximum for each factor, and multiply them together.

An abbreviated example: the least number that is divisible by 18 and 16:

18: { 3: 2, 2: 1 }
16: { 2: 4 }

maximums of factor repetitions: { 3: 2, 2: 4 }
result: 3^2 * 2^4 = 144

Factorising numbers from 2 to 20 is easy; if you don't know how to do it, there are many possible algorithms, you can see the Wikipedia article on integer factorisation for ideas.

Upvotes: 1

Related Questions