So, my question is to find the smallest multiple that divides evenly into all numbers from 1 through 20. I did solve the task successfully, but my program ran rather slow. Here is the code, the final number for n i used was 100 million. As you can imagine, that takes a lot of time. So I wanted to know, how i would optimize this code? Additionally, it would be nice to know how to change the number of numbers it should divide into, so instead of 1 through 20 let's say 1 through 15.

function smallestMultiple(n) {
    for (i = 0; i< n; i++) {
        if (i%1 === 0 && i%2 === 0 && i%3 === 0 && i%4 === 0 && i%5 === 0 
                 && i%6 === 0 && i%7 === 0 && i%8 === 0 && i%9 === 0 
                 && i%10 === 0 && i%11 === 0 && i%12 === 0 && i%13 === 0 
                 && i%14 === 0 && i%15 === 0 && i%16 === 0 && i%17 === 0 
                 && i%18 === 0 && i%19 === 0 && i%20 === 0 ) {

            console.log(i);
        }
    };
};

Now, obviously, this took over 5 minutes to find the answer. I wanted to know if there was a way more efficient way? EDIT: Obviously i could have used a variable for 1-20 as well. Will look into that, if you have an answer please thoroughly explain your answer and why it is more efficient.

So, my question is to find the smallest multiple that divides evenly into all numbers from 1 through 20. I did solve the task successfully, but my program ran rather slow. Here is the code, the final number for n i used was 100 million. As you can imagine, that takes a lot of time. So I wanted to know, how i would optimize this code? Additionally, it would be nice to know how to change the number of numbers it should divide into, so instead of 1 through 20 let's say 1 through 15.

function smallestMultiple(n) {
    for (i = 0; i< n; i++) {
        if (i%1 === 0 && i%2 === 0 && i%3 === 0 && i%4 === 0 && i%5 === 0 
                 && i%6 === 0 && i%7 === 0 && i%8 === 0 && i%9 === 0 
                 && i%10 === 0 && i%11 === 0 && i%12 === 0 && i%13 === 0 
                 && i%14 === 0 && i%15 === 0 && i%16 === 0 && i%17 === 0 
                 && i%18 === 0 && i%19 === 0 && i%20 === 0 ) {

            console.log(i);
        }
    };
};

Now, obviously, this took over 5 minutes to find the answer. I wanted to know if there was a way more efficient way? EDIT: Obviously i could have used a variable for 1-20 as well. Will look into that, if you have an answer please thoroughly explain your answer and why it is more efficient.

• javascript
• algorithm
• modulo

• 1 lcm(1, lcm(2, lcm(3, ...))), where lcm is the least mon multiple. – Oriol Commented Jul 30, 2015 at 23:25
• 1 Take your biggest number (in this case 20) and change your for like this: for (i = 0; i< n; i +=20 ) – Hassan Khodadadeh Commented Jul 30, 2015 at 23:25
• 1 You should break out of the for loop when you find the first successful number. – Barmar Commented Jul 30, 2015 at 23:33
• 1 You don't have to check the modulo for any non-prime numbers - %18 is redundant because when i%9 == 0 we already know that i%(9*2) == 0 – dave Commented Jul 30, 2015 at 23:35
• You don't need to test against all the numbers that are multiples of each other. If n is a multiple of 20, then it's also a multiple of all its factors, so you don't need to test 2, 4, 5, and 10. – Barmar Commented Jul 30, 2015 at 23:36

3 Answers 3

I think I found one of the most elegant solutions, straight from the forum:

Without actually trying it, I imagine that a few of the "brute force" methods here violate the "1 minute rule". However, considering a minor change can greatly improve the efficiency of the algorithm.

The "brute force" approach is assumed to be: iterate over each natural number - if the current is evenly divisible by each of the numbers 1 through 20, you've found your answer.

Consider this: if you know that the solution for N is X, then the solution for N+1 must be divisible by X. Therefore, when iterating through the natural numbers, you can iterate by X instead of 1. And instead of checking for the divisibility of the numbers 1 to N+1, you only have to check for N+1, since you already know that the values (multiples of X) are all divisible by 1 to N.

As an example, given that the answer for 10 is 2520, to get the solution of 11, we check if 2520 is evenly divisible by 11. It isn't, we iterate to 5040 and check if that is divisible by 11. We continue until we discover that 27720 is divisible by 11, which is out answer.

Despite making no attempt to directly determine LCDs, this ends up being a fairly speedy algorithm, running easily under a second for somewhat larger values of N.

In Ruby (though a similar approach can be used in many high-level languages):

def snd(max) result = 1 for n in 1..max prev = result while result % n > 0 result += prev end end return result end

puts snd(20)

I then interpreted that into Javascript and got this script

console.log("Please type in smallestMultiple(n), whereas n is the smallest multiple.");

function smallestMultiple(n) {
   var result = 1;
   var prev;
   for (i=1; i<n+1; i++) {
       prev = result;
       while (result%i > 0) {
           result += prev;
       }
   }
   console.log(result);
};

<script src="https://getfirebug./firebug-lite-debug.js"></script>

EDIT: Found an error in the script that would return smallestNumber(11) = 2520. Fixed in the for loop: for(i=0; i<n+1 ;i++)

Using the method of reduction by the greatest mon divisor

Skipping numbers 1 - 10 because you can multiply any of them by 2 and get another factor in the list.

function GCF(a, b) {
    if (b == 0) return a;
    else return (GCF (b, a % b));
}

function LCM(a, b) {
    return Math.abs(a*b) / GCF(a, b);
}

LCM(11, LCM(12, LCM(13, LCM(14, LCM(15, LCM(16, LCM(17, LCM(18, LCM(19, 20)))))))));

To do it for an arbitrary n, not super optimized but it is as simple as:

function LCM_N(n) {
    var x = 1;
    while (n > 1) {
        x = LCM(n, x);
        n--;
    }
    return x;
}

So, you want the least mon multiple of 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

This is the same as the least mon multiple (LCM) of 20,19,18,17,16,15,14,13,12,11 because 1,2,3,4,5,6,7,8,9,10 are all factors of the other ten numbers.

You should use a while loop, because they are faster.

The LCM must be less than or equal to the multiple of 20,19,18,17,16,15,14,13,12,11, so n can be started equal to that.

i can be started at the multiple of all of the primes in the sequence: 19*17*13*11*7*5*3*2

break out of the loop. This is probably what made it take so long for you.

We can increment by 20, because it is the smallest possible difference between answers.

function lowestCommonMultipleof20Through1(){
  var i = 19*17*13*11*7*5*4*3; 
  var n = 20*19*18*17*16*15*14*13*12*11;
  while(i < n){
    if( i%11 === 0 && 
        i%12 === 0 && 
        i%13 === 0 && 
        i%14 === 0 && 
        i%15 === 0 && 
        i%16 === 0 &&
        i%17 === 0 &&
        i%18 === 0 &&
        i%19 === 0 &&
        i%20 === 0 ){
      console.log(i);
      break;
    }
    i+=20;
  }
}

I got 232792560 almost instantly.