Project Euler Problem #5 Solution in C++

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;



3 Answers
3

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

main()

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

"stdafx.h"

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

for

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

contine

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

int

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

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

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:

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:

#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';



n=115

unsigned long

n=159

unsigned long

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.

"stdafx.h"

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.

continue

if

else

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?

int

INT_MAX

unsigned long

<cstdint>

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

int

#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).

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

std::lcm(m, n)

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



for (auto current = 2u; current <= limit; ++current) answer = std::lcm(answer, current++);

std::lcm()

limit==86

static

int

auto

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.