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.
upperBound
, but increment the target byupperBound
once you find one that does work for it. You'll then only check numbers divisible by20
, which means you check 1/20 of the numbers. \$\endgroup\$ – user34073 May 9 '17 at 19:08