Project Euler LCM of 1..20, with some guesswork

Question

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;
}     

Answer 1

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 Algorithm^{See 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.

Answer 2

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.

Answer 3

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.

Answer 4

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
}