Project Euler Problem 5: Smallest Multiple of 1 through 20

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());
}

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;
}
}
}

• Start at upperBound because it is more likely to fail – paparazzo May 9 '17 at 13:45
• Not only start at upperBound, but increment the target by upperBound once you find one that does work for it. You'll then only check numbers divisible by 20, which means you check 1/20 of the numbers. – Hosch250 May 9 '17 at 19:08

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

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

• The numer 2521 is not a magic number, it's named and it's called testNumber. Improving brute-force by skipping numbers by ceretain criteria is no longer brute-force but math and no brute-force has any chances against math. It's cheating when you still call it brute-force. – t3chb0t May 9 '17 at 9:53
• It is a magic number in the sense that it appears out of nowhere without explanation. There is no reasoning in the code as to why it is there. If used, it should've been a constant with some explanation, unless you like magic numbers sprinkled out in your code. – holroy May 9 '17 at 9:56
• @t3chb0t, And you are still brute forcing the solution even when you are skipping a few of the candidates. – holroy May 9 '17 at 9:58
• Regarding Comment your code. I've read that code should not state what is being done, that should be self-evident. Rather comments should explain why it's being done that way. Do you mean adding a description for the method as shown here. – IvenBach May 9 '17 at 17:35
• @IvenBach A comment stating "For loop from 1 to 20" is superfluous, a comment like "Loop through all candidates", or as given in my answer "checks whether value a proper factor of all the numbers in the range lowerBound to upperBound" are something else. They can describe the what or the why, or simply help those reading the code understand what is happening in the next code segment (or method). – holroy May 9 '17 at 18:35

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)) ;

• I would strongly emphasize that you can do the pre-increment, but I wouldn't suggest doing so, as having that empty while body really cripples the reading and understanding of the code. – holroy May 9 '17 at 8:51
• @holroy I'm of a different opinion ;-) – t3chb0t May 9 '17 at 8:53
• Knowing that something can be done is very beneficial. For my sake, I'll err on the side of caution and wrap it { ... } to explicitly show what's going on. – IvenBach May 9 '17 at 17:19

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.

• If you're going to change the increment, you could at least apply the logic fully and set the increment to 2520. – Peter Taylor May 9 '17 at 8:35
• @PeterTaylor I think I was so preoccupied with getting to the suggestion about throwing away the brute force that I've ended up being a bit dim. I'll update my answer. – RobH May 9 '17 at 9:23