Project Euler #5 - Lowest Multiple of 1 through 20

Question

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 < 1000000000; x++) {

            bool dividable = true;

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

            }
            if (dividable == true) {
                Console.WriteLine (x);
            }
        }
    }

Answer 1

There are a few obvious things:

1. You loop from 20 to 0 every time. You only need to loop from 20 to 2 -- every number is evenly divisible by 1.

2. You divide every number from everything from 20 to 0. If it's not divisible by 20, why check if it's divisible by 19, 18, 17, etc? It already failed.

3. Only numbers ending in 0 are divisible by 10. You can eliminate a lot of possibilities right off the bat by checking for that. In fact, you can just increment by 10 every time. You've just cut the amount of numbers you're checking by an order of magnitude.

4. Only numbers ending in 0 or 5 are divisible by 5.

There's a whole list of divisibility rules: http://en.wikipedia.org/wiki/Divisibility_rule

I think just fixing those obvious things will be enough to see a significant increase in overall performance.

Answer 2

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 <= 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.

Answer 3

The root idea is to factorize all numbers in the range from 2 to 20 to the prime numbers with their multiplicity and find their production (with the multiplicity). The resulting number must be evenly divisible by all of the numbers from 1 to 20.

Get all primes from the range:

private static int[] GetPrimes(int n)
{
    BitArray a = new BitArray(n + 1, true);

    for (int i = 2; i <= Math.Sqrt(n); i++)
    {
        if (a[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                a[j] = false;
            }
        }
    }

    List<int> primes = new List<int>();
    for (int i = 2; i < a.Length; i++)
    {
        if (a[i])
            primes.Add(i);
    }

    return primes.ToArray();
}

This method gets all dividers (with multiplicity) of a given number:

private static IEnumerable<Tuple<int, int>> GetUniqueDividers(long n)
{
    List<int> tmp = new List<int>();
    List<int> pows = new List<int>();
    foreach (int p in Primes)
    {
        while (n != 1)
        {
            long rem = n % p;
            if (rem == 0)
            {
                n /= p;
                if (!tmp.Contains(p))
                {
                    tmp.Add(p);
                    pows.Add(1);
                }
                else
                    pows[tmp.IndexOf(p)]++;
            }
            else
                break;
        }
    }
    return tmp.Select((v, i) => new Tuple<int, int>(v, pows[i]));
}

The initialization:

private const int Max = 20;
private static readonly int[] Primes = GetPrimes(Max);

The method body:

int[] counts = new int[Max + 1];
for (int i = 2; i < counts.Length; i++)
{
    foreach (var div in GetUniqueDividers(i))
    {
        if (counts[div.Item1] < div.Item2)
        {
            counts[div.Item1] = div.Item2;
        }
    }
}

int outNumber = 1;
for (int i = 2; i < counts.Length; i++)
{
    if (counts[i] != 0)
    {
        outNumber *= (int)Math.Pow(i, counts[i]);
    }
}

Answer is in the outNumber variable.

Answer 4

Let's go through some basic rules:

• Everything is divisible by 1.
• If something is divisible by 16, then it's divisible by 2, 4, and 8.
• If something is divisible by 9, then it's divisible by 3.
• If something is divisible by both 16 and 9, then it's divisible by 6, 12, and 18.
• If something is divisible by both 16 and 5, then it's divisible by 10 and 20.
• If something is divisible by both 16 and 7, then it's divisible by 14.
• If something is divisible by both 9 and 5, then it's divisible by 15.

That leaves: 5, 7, 9, 11, 13, 16, 17, 19. Multiply those together and you get

232,792,560

Which of course is the answer.

Some of the other answers may have written the code to generate this list in general (i.e. for values other than 20). They don't seem to have commented the code in a way that's making it clear to me what they're doing.

Answer 5

Seems like I am a little bit late, but I would use a completely different approach(as if i would do with a pencil and paper) which returns the result immediately

Console.WriteLine(Calc(10));
Console.WriteLine(Calc(20));

---

List<int> Factors(int n)
{
    List<int> list = new List<int>();
    int i=2;
    while(i<=n)
    {
        if (n % i == 0)
        {
            list.Add(i);
            n /= i;
        }
        else
            i++;
    }
    return list;
}

int  Calc(int n)
{
    var factors = Enumerable.Range(2, n-1).Select(j => Factors(j)).ToList();

    int i = 2;
    int res = 1;
    while (i <= n)
    {
        if (factors.Count(l => l.Contains(i)) > 1)
        {
            factors.ForEach(l => l.Remove(i));
            res *= i;
        }
        else
            i++;
    }

    return res * factors.SelectMany(x => x).Aggregate((s, j) => s *= j);
}

Answer 6

I know I'm late, but you can:

1. Only test 11-20, since if 12 is divisible, 6 is as well. if 14 is, then 7 is. etc.

2. Count by 20s, since 20 is the largest number and it can't be divisible by anything between 0 and 20, 20 and 40, 40 and 60, etc.

3. Don't test all the numbers; stop once you find one to not work. Also don't test 20 if you apply #2 since you know it'll work.

Answer 7

Just compute the lcm of all numbers from 1 to 20.

LCM of (a, b) is (a * b)/gcd(a, b) and the Euclids's algorithm for GCD is one of the earliest algorithm thaught in a class about functions and recursion.

I am not fluent in C# but here is an example in Scala :

object Euclid extends App {

       def gcd(a: Long, b: Long): Long = {  
           if (b == 0) a else gcd(b, a % b)
       }

       def lcm(a: Long, b: Long) = (a / gcd(a, b)) * b

       var answer = 1l
       for (i <- 2 to 20) answer = lcm(answer, i)

       println(answer)
}

Evaluating the complexities of algorithms is a must when trying to solve that kind of problems.

The complexity of Euclid's algorithm can be approximated by \$O(log(max(a,b)))\$. The LCM of numbers from 1 to n can be calculated in \$O(n.log(n))\$ steps and I think that this approach is the best proposed so far.

OK, here is a solution in Java, which should be more readable to a C# programmer:

public static int gcd(int a, int b) {
  if (b == 0) return a; else return gcd(b, a%b);
}

public static int lcm(int a, int b) {
  return b*(a/gcd(a, b));
}

public static int euler() {
  int answer = 1;
  for (int i = 2; i <= 20; i++) {
     answer = lcm(answer, i);
  }
  return answer;
}

[edit] Original code could overflow, be careful to use longs and doing the division before the multiplication in LCM.

Answer 8

Add a break statement when the test fails in your inner loop.

Answer 9

There's a few key optimisations that, on my machine, takes the execution time of your function down to 10 seconds (my 2.5 GHz Intel Core i7).

Check out your main loop; you're incrementing the possibilities with ++, but since you know the answer must be a multiple of 20, so why not start at 20, then increment with x+=20; then just check if it's divisible by 19, 18, etc. This gives you a 20x speedup.

Second, you don't need to check every factor; if your x is divisible by 20, then it's also divisible by 10; if it's divisible by 18 it's divisible by 9; if it's divisible by 16 then it's divisible by 8. And so on. So the only factors you need to check are 20..11. 10...1 are already covered. (BTW, going from 20 down is a good direction.)

Third, quit out as soon as it's proved not a suitable candidate. That's the biggest gain.

        for (long x = 20; true; x+=20) {
                bool dividable = true;

            for (int y = 20; y >= 11; y--) {
                if (x % y != 0) {
                    dividable = false;
                    break;
                }
            }

            if (dividable == true) {
                Console.WriteLine(x);
                break;
            }
        }