Project Euler Problem 5: Smallest Multiple of 1 through 20

Question

In continuing to learn C# I solved Problem #5 with my code below. I tried to follow the suggestion to write [my] program so that it looks like the specification. Where can I improve my code?

The problem is as follows:

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?

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(GetSmallestEvenlyDivisibleNumber());
            Console.ReadLine();
        }

        static bool isEvenlyDivisible(int value, int lowerBound, int upperBound)
        {
            bool returnValue = true;
            for (int i = lowerBound; i<= upperBound; ++i)
            {
                if (value % i != 0)
                {
                    returnValue = false;
                    break;
                }
            }

            return returnValue;
        }

        static int GetSmallestEvenlyDivisibleNumber(int lowerBound = 1, int upperBound = 20)
        {
            int testNumber = 2521;

            while (!isEvenlyDivisible(testNumber, lowerBound, upperBound))
            {
                testNumber += 1;
            }

            return testNumber;
        }
    }
}

Answer 1

Two focus areas for this review, first some style and code comments, and then a little discussion on a more optimal solution.

Code and Style Comments

• Mostly good and clean code – I like to see clean, properly spaced, well named code, as it makes it a whole lot easier to understand (and easier for you to maintain in the long run).
• Stick to PascalCase – This is already commented upon in another answer, but having equal naming and standards throughout your code really helps readability and eases the understanding of code. Which in turns, makes your code maintable.
• Avoid magic numbers – Within GetSmallestEvenDivisibleNumber() you use 2521. This number pops out of nowhere in the context of the code. Not good. In addition, it introduces a bug if you try to find the solution for any range with upperBound < 10.
• Comment your code – It is not given what the IsEvenlyDivisible method actually does, and I would spend some time commenting upon what it does. Something along the lines of Checks whether value is a proper factor of all the numbers in the range lowerBound to upperBound.

Alternate Solution

Most Euler problems have at least two major solution: The brute force solution, and an optimal solution. You've implemented the brute force of testing each and every number to see if it matches the criteria. In some cases the brute force can be improved somewhat, like skipping all the odd numbers, check for ending of 0 or 5, verify that the value is dividable by 3, and so on... This will usually lead to a somewhat faster solution, but when tackling the higher Euler Problems that'll not be enough.

Therefore it is a good idea to start looking for optimal solutions, and what is really asked for. In this case what is the number 2520, and how have they derived at it? So what we now about that number:

• Is is dividable by the numbers in the range 1 through 10
• By nature of previous statement, it also needs to be dividable by all of the factors of each of numbers in the range, so let us decompose the range:

\begin{align} 1 & \rightarrow 1 \\ 2 & \rightarrow 2 \\ 3 & \rightarrow 3 \\ 4 & \rightarrow 2 * 2 \\ 5 & \rightarrow 5 \\ 6 & \rightarrow 2 *3 \\ 7 & \rightarrow 7 \\ 8 & \rightarrow 2*2*2 \\ 9 & \rightarrow 3*3 \\ 10 & \rightarrow 2 * 5 \end{align}

• Grouping these factors we find that we have 3 * 2's, 2 * 3's, 1 * 5, and 1 * 7. Based upon these factors, we can compose any of the range, and as it turns out: \$ 2 * 2 * 2 * 3 * 3 * 5 * 7 = 8 * 9 * 5 * 7 = 2520\$

In other words if you decompose each of the numbers of your range, and then count how many of each you need to create each of the numbers, this can be used to calculate the answer directly.

To help you get on the way for the range 1 through 20 let us decompose the final numbers as well: \begin{align} 11 & \rightarrow \mathbf{11} \\ 12 & \rightarrow 2 * 2 * 3 \\ 13 & \rightarrow \mathbf{13} \\ 14 & \rightarrow 2 * 7 \\ 15 & \rightarrow 3 * 5 \\ 16 & \rightarrow 2 * 2 * 2 * \mathbf{2} \\ 17 & \rightarrow \mathbf{17} \\ 18 & \rightarrow 2 * 3 * 3 \\ 19 & \rightarrow \mathbf{19} \\ 20 & \rightarrow 2 * 2 * 5 \\ \end{align}

I've bolded the numbers not already present in our set, and those are \$11 * 13 * 17 * 19 * 2 = 92738\$. So the end result will be: \$92738 * 2520 = 232792560\$.

So there you have yourself a new challenge: Implement this alternate, but more efficient algorithm.

Answer 2

helper variable not necessary

static bool isEvenlyDivisible(int value, int lowerBound, int upperBound)
{
    bool returnValue = true;
    for (int i = lowerBound; i<= upperBound; ++i)
    {
        if (value % i != 0)
        {
            returnValue = false;
            break;
        }
    }

    return returnValue;
}

You don't need the returnValue here because you can return as soon as the condition is true like that:

static bool IsEvenlyDivisible(int value, int lowerBound, int upperBound)
{
    for (int i = lowerBound; i <= upperBound; ++i)
    {
        if (value % i != 0)
        {
            return false;
        }
    }
    return true;
}

---

preincrement

while (!isEvenlyDivisible(testNumber, lowerBound, upperBound))
{
    testNumber += 1;
}

This loop does not necessarily need to have a body. You can do the same with the ++ pre-increment operator inline:

while (!IsEvenlyDivisible(++testNumber, lowerBound, upperBound)) ;  

Answer 3

In terms of simply making your code better (keeping with the brute force approach) there are a couple things you could note.

1. You only need to check the even numbers because the answer is divisible by 2
2. Only numbers ending in 5 or 0 are divisible by 5

Putting those together we can see that the solution must be divisible by 10. That means we can start our search at 2520 and add 10 each time:

static int GetSmallestEvenlyDivisibleNumber(int lowerBound = 1, int upperBound = 20)
{
    int testNumber = 2520;

    while (!isEvenlyDivisible(testNumber, lowerBound, upperBound))
    {
        testNumber += 10;
    }

    return testNumber;
 }

Edit:

As Peter Taylor pointed out in the comments, you can take the logic further to incrementing by 2520 each time because the final solution needs to be divisible by all the numbers 1-10. However, the main thrust of my answer was supposed to be that you don't need to brute force and you can compute the solution directly.

---

Your code looks good: you have consistent spacing and good, descriptive names. isEvenlyDivisible should be IsEvenlyDivisible as all methods are PascalCase in C#.

I would remove the optional parameters from GetSmallestEvenlyDivisibleNumber as we've now made it much more specific to the case of 1-20.

You can calculate this directly without needing to brute force see this blog for a good explanation of that approach.