1
\$\begingroup\$

Project Euler problem #5 is the following:

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?

First, a disclaimer: yes, I know that there are much more optimal ways of solving this. This is a very dumb "brute-force" way to solve this that uses very little mathematical intelligence. If I did the analysis correctly (and please correct me if not), this solution is $$O(n^2)$$ With that said, I'm curious if anyone had any feedback on this (and again, I am familiar with the mathematically optimal way to do this). In particular, it seems like there should be a way to eliminate the while loop.

public class SmallestMultiple
{
    public long GetSmallestMultiple(int maxNumber)
    {
        long num = 1;

        for (int i = maxNumber; i >= 1; i--)
        {
            long modulo = num % i;
            if (modulo > 0)
            {
                num *= i;
            }
        }

        long prev = num;

        while (true)
        {
            // If dividing by this number wouldn't cause any "harm" (i.e. it's still actually a multiple of everything),
            // go ahead and do it
            for (int i = 2; i <= maxNumber; i++)
            {
                num /= i;

                for (int j = 2; j <= maxNumber; j++)
                {
                    if (num % j > 0)
                    {
                        num *= i;
                        break;
                    }
                }
            }

            if (prev == num)
            {
                break;
            }
            else
            {
                prev = num;
            }
        }

        return num;
    }
}

And here's my unit test (written in Visual Studio):

[TestClass]
public class SmallestMultipleTests
{
    [TestMethod]
    public void SmallestMultipleTest()
    {
        SmallestMultiple multiple = new SmallestMultiple();

        long result = multiple.GetSmallestMultiple(10);

        Assert.AreEqual(2520, result);

        result = multiple.GetSmallestMultiple(20);

        Assert.AreEqual(232792560, result);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Why would you do a brute force on a Euler? \$\endgroup\$ – paparazzo Aug 9 '17 at 18:53
  • \$\begingroup\$ @Paparazzi Normally I wouldn't (kind of kills the point of the exercise), I just wanted to create one for that problem to see how it would compare to more optimal solutions. \$\endgroup\$ – EJoshuaS Aug 9 '17 at 18:57
5
\$\begingroup\$

The main problem with your code is that it's very hard to understand.

First of all, I'd expect GetSmallestMultiple(10) to return 10. After all, the smallest multiple of 10 is 10, right? That's how your code reads, when it's not really what you want to do. Maybe your signature should look something more like this :

public long GetSmallestCommonMultiple(IEnumerable<int> multiples)

This way, your code reads :

SmallestMultiple.GetSmallestCommonMultiple(Enumerable.Range(1,10));

Now I'd expect 2520 as an answer.

The thing with algorithms is that they can indeed be hard to read, even if it's just a brute force. To counter this, you need strong variable names and a logical flow in your algorithm. (Meaning that just by reading the code I can understand clearly every step of the algorithm)

For example, the code below, if I got it correctly, will find one common multiple (probably not the smallest one) of the multiples. Meaning that, for multiple = 10, we'd have : 10*9*8*7*6

for (int i = maxNumber; i >= 1; i--)
{
    long modulo = num % i;
    if (modulo > 0)
    {
        num *= i;
    }
}

Using the signature I explained at the beginning, we'd get something like that

long commonMultiple = 1;
foreach(var multiple in multiples)
    if(commonMultiple % multiple > 0)
        commonMultiple *= multiple;

Is it much clearer? Nope. What could we do to make it better? Nothing much, right? In such situations, add comments is a good thing to do.

Basically, I think you need to think of better variable names and try to make the algorithm more apparent in your code, now it's kind of hidden behind your code. I know this sounds weird, but usually you should be able to read code once or twice and get what the algorithm does. Now, I can't. I know what you're doing because I know what method you employed, but if I was to read this without barely no mathematic background I'd struggle to understand what's happening.

\$\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.