8
\$\begingroup\$

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);
            }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ How slow... is slow? ms? \$\endgroup\$ – Piotr Kula Oct 25 '14 at 19:03
  • \$\begingroup\$ I put a timer in the program, and it takes 7 minutes to get to the number 232792560 \$\endgroup\$ – Alexander Ameye Oct 25 '14 at 19:06
  • \$\begingroup\$ Yea I just tried that.. It does take a long time. Possibly threading will be the next step and applying some elimination rules as Daniel mentioned. \$\endgroup\$ – Piotr Kula Oct 25 '14 at 19:11
  • \$\begingroup\$ You can easily determine this by hand aswell, by breaking the numbers $1$ to $20$ down into their prime factors and looking at the greatest powers. So you will have 2^4,3^2,5,7,11,13,17,19. Multiply these together and you are done. Which is trivial when you consider that 2=2,3=3,4=2^2, 5=5, 6=2*3,7=7,8=2^3,9=3^2,10=2*5,11=11,12=3*2^2,13=13,14=2*7,15=3*5,16=2^4,17=17,18=2*9,19=19,20=2^2*5 \$\endgroup\$ – user56907 Oct 26 '14 at 22:40
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ OK, this may speed up the code, but can it be millions of times as suggested in other answers? \$\endgroup\$ – I4V Oct 25 '14 at 21:15
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This should be marked as the answer. \$\endgroup\$ – Dimesio Jul 23 '15 at 17:37
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It's easier to find all primes under 20 and rise them to whatever power that still leaves the number under 20, in code that is. \$\endgroup\$ – Simon Dec 6 '16 at 20:03
3
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ I'll take a look at it, but thank you for your respons, it's very much appreciated! :D \$\endgroup\$ – Alexander Ameye Oct 25 '14 at 19:38
  • \$\begingroup\$ +1 We are thinking in the same manner. One little note: if you'll use only prime numbers, it could be ~2 times faster. See my answer below. \$\endgroup\$ – Dmitry Oct 25 '14 at 20:04
  • \$\begingroup\$ @Dmitry You may be right, but I think, reducing 7 mins to a few micro seconds is enough :) \$\endgroup\$ – L.B Oct 25 '14 at 20:34
  • 1
    \$\begingroup\$ Although this answer provides an alternative way of implementing what the OP wants, commenting on what things you do differently, why you are doing it that way and pointing out the flaws in the OP's original code would make this a better answer. Simply providing a different way to do things without explaining them does not always provide a good learning experience. \$\endgroup\$ – Simon Forsberg Oct 26 '14 at 17:06
  • \$\begingroup\$ @SimonAndréForsberg You are right, but I didn't want to post a complete copy-paste-ready answer including all explanations. I think OP should think how this code runs millions of times faster than his code.. \$\endgroup\$ – L.B Oct 26 '14 at 22:24
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ And how would you extend your post to answer the question, other than copying and pasting the GCD code from somewhere? \$\endgroup\$ – I4V Oct 25 '14 at 21:41
  • \$\begingroup\$ Err, my post does answer the question! I give the functions for calculating GCD and LCM of two numbers, and a function to calculate the LCM of several numbers \$\endgroup\$ – scand1sk Oct 25 '14 at 21:49
  • \$\begingroup\$ So if I call it as gcd(1,20) will I get the answer :) \$\endgroup\$ – I4V Oct 25 '14 at 21:51
  • \$\begingroup\$ No, the for loop at the end of the code actually computes the answer using the LCM function above. \$\endgroup\$ – scand1sk Oct 25 '14 at 21:53
  • \$\begingroup\$ @Then why don't you post that loop? The question is not about LCM (Of course as other answer replies, it is about using LCM) \$\endgroup\$ – I4V Oct 25 '14 at 21:53
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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;
            }
        }
\$\endgroup\$

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.