Project Euler Problem #5 Solution in C++

Question

Project Euler #5: Smallest multiple

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?"

And I'm wondering if my code to solve this problem is good and if there are ways to make it better.

#include "stdafx.h"
#include <iostream>
int main(){
int smallestMultiple = 40;
int i = 10;
while (i<20){
 if (smallestMultiple%i == 0){
 i++;
 continue;
 }
 else{
 i = 10;
 smallestMultiple += 20;
 }
 }
std::cout << smallestMultiple;
}

• Martin R: There are far more efficient ways to get the result. I would suggest to have a look at existing Q&A's about the same problem, such as codereview.stackexchange.com/q/80500/35991.

Answer 1

First reviewing the code itself:

1. First, fix the indentation, and insert an empty line before your main(). Proper formatting is a most basic step allowing easier comprehension.

2. "stdafx.h" is part of the MSVC-support for pre-compiled headers. Your project is so small it cannot really take advantage of that anyway, so it's just a wart.

3. Use the right loop for the job. A for-loop seems to fit better, as you have init (with declaration), condition, next, and body.

4. Don't use contine where it has no effect, nor clarifies intent.

5. In general, int is too small for your result. Luckily(?), on Windows it's 32 bit, which should suffice.

6. Put the calculation into its own function for re-use.

7. Don't forget to output a newline at the end, it's expected and omitting it might have interesting effects.

And then the algorithm:

Testing every 20^th number whether it's the target is supremely inefficient. Even using steps of 2520 instead isn't that much better.
Consider constructing the result instead:

1. r = 1
2. For i = 2 to the limit
   • If i does not divide r
     • Multiply r by the highest integer-power of i not exceeding the limit.

Keeping in mind that Project Euler is not really for brute-force or straight-up coding, but figuring out an intelligent approach for manually calculating things:

1. 2520 is the least common multiple of the numbers 1 through 10.
2. Go through 11 to 20, and figure out whether you need an additional factor.
   Observation: 4 times the number itself (it's prime), once the fourth root.
3. That's easily put into a calculator, for the result 232792560.

Putting it all together:

#include <iostream>
static unsigned long lcm_until(unsigned n) noexcept {
 auto r = 1UL;
 for (auto i = 2UL; i <= n; ++i) {
 if (r % i) { // i is prime
 auto x = i;
 while (x * i <= n)
 x *= i;
 r *= x;
 }
 }
 return r;
}
int main() {
 std::cout << lcm_until(20) << '\n';
}

• Toby Speight: Much better code - it does break down without warning after n=115 on this system with 64-bit unsigned long (or after n=159 with 128-bit unsigned long). Of course, the original code would take years to get to those values...

Answer 2

Code Review

Despite its name, "stdafx.h" isn't a standard header. It doesn't seem to be needed, as the code compiles and runs without it.

Your indentation is off - perhaps that's a result of how you inserted the code into the question?

The continue is redundant - there's no more code within the loop after the if/else, so it can be omitted.

The code assumes that a result will be found before int overflows. Remember that INT_MAX may be as small as 32767; perhaps unsigned long may be a better choice, or one of the fixed-width types specified in <cstdint>, perhaps?

Your loop structure would be clearer if you separate out the test from incrementing smallest multiple. That could look something like this (still using int as our type):

#include <iostream>
#include <climits>
static bool is_multiple_of_all(int n, int max)
{
 for (int i = 10; i <= max; ++i) {
 if (n % i != 0) {
 return false;
 }
 }
 return true;
}
int main()
{
 const int target = 20;
 for (int candidate = 2 * target;
 candidate <= INT_MAX - target;
 candidate += target)
 {
 if (is_multiple_of_all(candidate, target)) {
 std::cout << candidate;
 return 0;
 }
 }
 // not found
 return 1;
}

Algorithm

Project Euler problems tend to exercise your mathematical reasoning. You're expected to find better methods than brute force search to find the solution. (Hint: think about prime factors).

Answer 3

Another way to approach this, is to use the std::lcm(m, n) (c++17) function. Start with 2520 and 11:

#include <numeric>
using std::lcm;
typedef unsigned long long ull;
ull solve()
{
 static const int limit = 20;
 static int current = 11;
 static ull answer = 2520;
 if (current > limit)
 {
 return answer;
 }
 answer = lcm(answer, current++);
 return solve();
}

• Toby Speight: That appears to be a single-use function. I wouldn't advise that, because it makes it hard to generalise to one that accepts an argument. Besides, it's much clearer in iterative form: for (auto current = 2u; current <= limit; ++current) answer = std::lcm(answer, current++);. Do note that std::lcm() gives wrong results from only limit==86, so we have less range when we use this function.
• Deduplicator: static state to avoid direct Iteration? Evil. Also, an int is potentially too small. And I'm not sure memoizing the solution is a good idea at all. Also, a using-declaration for a function used once, a typedef better replaced by more generous use of auto, and an aversion to empty lines? hm...