Project Euler #5 - Lowest Multiple of 1 through 20 I was trying to solve problem 5 of Project Euler, and this was I needed to do:


  2520 is the smallest number that can be divided by each of the numbers
  from 1 to 10 without any remainder.
  
  What is the smallest positive number that is evenly divisible by all
  of the numbers from 1 to 20?


I came up with a solution, and I get the correct answer in about 7 minutes, but my question is, how could I make it faster? Calculation speeds are incredibly slow, how could I optimize it?

        for (long x = 1; x &lt; 1000000000; x++) {

            bool dividable = true;

            for (int y = 20; y &gt; 0; y--) {
                if (x % y != 0) {
                    dividable = false;
                } 

            }
            if (dividable == true) {
                Console.WriteLine (x);
            }
        }
    }
A number of answers have pointed out some algorithmic changes, and some logic steps you can take, to calculate the result, but there's a simpler way to do it, which is not necessarily the fastest way, but it is still blazingly fast, and still very simple.

The algorithm you have by testing every number is obviously overkill, but, what about going through the basics of the process, and implementing it in code. What is the question actually asking? It's asking for the lowest common multiple of all the numbers 1 through 20.

Mathematically, 1 is a multiple of 1. so, we start there...

Then, find the multiple of 1 that is also a multiple of 2... to do that, we add the 1 to itself repeatedly, until we get a multiple of 2. This is easy, it is just once....

Now we have 2, which is a multiple of both 1, and 2. We want to find the multiple of both 1 and 2 (which is 2), that is also a multiple of 3, so, we check whether 2 is a multiple (it's not), so we add 2 to itself, which is 4. Is 4 a multiple? No, so we add 2 again, to get 6. Is 6 a multiple of 3? Yes. So, 6 is the lowest multiple of 1, 2, and 3. Now, we just repeat this process to 20.

Let's introduce some names here, lcm is the lowest common multiple, and sum is some value that is a multiple of lcm. If sum is a multiple of lcm, then it is also a multiple of everything that lcm is a multiple of.

The rest is actually easier to understand with code....., and it can be generalized very easily with a method like:

public static int GetLCM(int from, int to) {
    // lcm is the Lowest Common Multiple, which starts as just 'from'
    var lcm = from;
    for (int i = from; i &lt;= to; i++) {
        var sum = lcm;
        while (sum % i != 0) {
            sum += lcm;
        }
        // sum is now the first multiple of lcm that is also a multiple of i
        lcm = sum;
    }
    return lcm;
}


Now, I have taken that concept and implemented it on Ideone, and you can see that it arrives at the right solution, using a simple algorithm, in almost no time.