1
\$\begingroup\$

I'm doing a Euler challenge that is stating to find the smallest positive number that is divisible (without a remainder) by all numbers from 1 to 20. So I did it however, I don't like the fact that I have to guess up to which number the while loop have to go (var s.... s < 303000000) and I guess there are too many variables. I'm sure I could get rid of 's'.

var s = 0;
var n = 1;

while (s < 303000000) {
        for (var i=1;i<21;i++) {
                if (n % i != 0) {
                        break;
                }
                if (i == 20) {
                        console.log(n);
                }
        }
        n += 1;
        s += 1;
}     
\$\endgroup\$
2
\$\begingroup\$

The below formula can be used to get the LCM of two numbers. See Reduction by the greatest common divisor section in Wikipedia

               a * b
lcm(a, b) = ―――――――――――
             gcd(a, b)

GCD can be calculated by using the Euclidean AlgorithmSee Using Euclid's algorithm section in Wikipedia.

gcd(a, b) = gcd(b, a % b)

Using these two formulas, the LCM can be calculated as follow

console.time('new');

function gcd(a, b) {
    while (b !== 0) {
        var temp = a;
        a = b;
        b = temp % b;

        // Can be written in ES6 as
        // [a, b] = [b, a % b];
    }

    return a;
}

function lcm(a, b) {
    return a * b / gcd(a, b);
}
var range = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
console.log(range.reduce(lcm, 1));
console.timeEnd('new');

This is very efficient than using while and for, see this JsFiddle demo.

Note: This answer is inspired by this and this posts.

\$\endgroup\$
1
\$\begingroup\$

Well, if you knew beforehand when to stop the loop, you'd have your solution already, right?

Also:

  • You're just logging the number, I think you should stop the outer loop when you've found the solution.

  • Why do you even need to check a number for the outer loop? Sooner or later you're going to find a solution, so just keep going until you find it.

  • As the other answer said, it has to be a multiple of 21, but since there's a 10 in there, it actually has to be a multiple of 210.

My suggestion if you really want to use brute force:

var found = 0;
var n = 0;

while (!found) {
    n += 210;
    found = 1;
    for (var i=1;i<21;i++) {
        if (n % i != 0) {
            found = 0;
            break;
        }
    }
}   
console.log(n);

If you don't want to use brute force, but prime factorization and/or LCD determination, you can have a look at this answer. That's java, but the algorithm is valid.

\$\endgroup\$
1
\$\begingroup\$

There's a few things you can do to improve this.

For your 'I have to guess up to which number the while loop have to go' problem, instead of going until you reach a specific number, you can tell it to go until you have an answer. You have your answer when i == 20, so if you initialize i outside the loop and you have it loop while(i !== 20), then it will just stop when you find the answer.

I'm not sure why you have separate variables for n and s. They seem to have the same function.

Another thing you can do is have your counter start at 20 (there's no way any number under 20 is divisible by all these numbers) and increase by 20 each iteration (skipping over all the numbers not divisible by 20 entirely).

edit: another answer that was posted while I was writing this says that you should increment your counter by 21. That is incorrect, 21 is not divisible by 20. I'd comment on that answer but I don't have the reputation to do that.

edit 2: another answer said it has to be over 210 (21 * 10) this is also incorrect because 20 is divisible by both. Maybe I'm misunderstanding the challenge here. If that's the case, somebody please let me know.

\$\endgroup\$
  • \$\begingroup\$ Well, if I understood the question correctly, the fact that 20 is divisible by both is exactly the reason why you can increment by 210 :-) You can actually increment it further, but by that way you're basically calculating the solution yourself by hand, because at some point you will increase exactly by "the smallest positive number that is divisible by all numbers from 1 to 20". \$\endgroup\$ – ChatterOne Oct 13 '16 at 7:57
  • \$\begingroup\$ The solution doesn't have to be a multiple of 210 though, it has to be a multiple of 20. 210 isn't even divisible by 20. \$\endgroup\$ – suddjian Oct 13 '16 at 7:59
  • \$\begingroup\$ You're right. I guess we can increment by 420 then, but the basic idea stays the same. \$\endgroup\$ – ChatterOne Oct 13 '16 at 9:44
  • \$\begingroup\$ incrementing by 420 would skip over a large number of potential candidates. Multiples of 420 are not the only numbers divisible by both 20 and 10. \$\endgroup\$ – suddjian Oct 13 '16 at 17:53
1
\$\begingroup\$

n and s

You don't need s, because You increment n and s in every loop.

var n = 1;

while (n < 303000001) {
  for (var i = 1; i < 21; i++) {
    if (n % i != 0) {
      break;
    }
    if (i == 20) {
      console.log(n);
    }
  }
  n += 1;
}

Optimization 1

Because n must be divisible by all numbers from 1 to 20, n must be a multiple of 21, and You can start from 21

var n = 21;

while (n < 303000001) {
  for (var i = 1; i < 21; i++) {
    if (n % i != 0) {
      break;
    }
    if (i == 20) {
      console.log(n);
    }
  }
  n += 21;
}

Optimization 2

n must be divisible by all numbers from 1 to 20. If n is divisible by 2 and 4, then n is divisible by 8. In this case You can't check 2 and 4. We finally being checked 11 to 20:

var n = 21;

while (n < 303000001) {
  for (var i = 11; i < 21; i++) {
    if (n % i != 0) {
      break;
    }
    if (i == 20) {
      console.log(n);
    }
  }
  n += 21;
}

Optimization 3

n must be divisible by all numbers from 1 to 20. In this case You can start from and step by 3*5*7*11*13*17*19 (prime numbers from 1 to 20)

Instead of for loop You can use Array.some function

var step = n = 3 * 5 * 7 * 11 * 13 * 17 * 19;
var tab = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
var predicate = function(i) {
  return n % i !== 0
}

while (n < 303000001) {
  if (!tab.some(predicate)) {
    console.log(n)
    return
  }
  n += step
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Optimisation 4: because the range 1 to 20 starts at 1 and doesn't miss any numbers out, each prime power which divides the LCM is in that range. So we have console.log(16 * 9 * 5 * 7 * 11 * 13 * 17 * 19). \$\endgroup\$ – Peter Taylor Oct 13 '16 at 11:06
  • \$\begingroup\$ Hah. I knew that there was something like that hiding around, thanks for pointing that out. \$\endgroup\$ – ChatterOne Oct 13 '16 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.