# Project Euler #5 in C++

I'm currently doing the Project Euler challenges to learn C++. The fifth problem is the following.

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?

I thought of a loop between 20 and 10 as everything under 10 is a multiple of something under 10. At each iteration, the result is the lcm of the loop variable and the current result.

If I am correct, the complexity of this should be $$\\mathcal{O}(n/2)\$$. Am I right?

Is there any faster/better/cleaner implementation or another algorithm with a better complexity?

This is my code.

#include <iostream>

long gcd(long a, long b)
{
long t;

if (b == 0) return a;

while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}

long lcm(long a, long b)
{
return (a * b) / gcd(a, b);
}

int main()
{
long n(20), result(1);
for (long i = n; i > n/2; --i) {
result = lcm(result, i);
}
std::cout << "Result: " << result << "\n";
}


Welcome to Code Review! This is actually pretty good code for a beginner, but here are some things that may help you improve your program.

## Simplify the code

The gcd routine looks like this:

long gcd(long a, long b)
{
long t;

if (b == 0) return a;

while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}


It can be simplified in three ways. First, we can declare t within the loop. Second, we can eliminate the if statement entirely. Third, we can simplify the while loop condition to simply while (b) which is the same as while (b != 0):

long gcd(long a, long b)
{
while (b) {
long t = b;
b = a % b;
a = t;
}
return a;
}


## Use const where appropriate

The value of n is constant, so it would make sense to declare it either const or even better constexpr.

## Consider signed versus unsigned

It's always worth thinking about the domain of the numbers in a calculation. In this case, it seems that all of the numbers are probably intended to be unsigned, but they're declared long which gives signed numbers.

## Think of alternative algorithms and implementations

I think your algorithm is fast enough, but an alternative approach would instead be to calculate all of the unique prime factors of all of the numbers < 20 and simply multiply them together. With the judicious use of constexpr, one could even calculate everything at compile-time which would make for a very fast calculation. For inspiration, see Compile-time sieve of Eratosthenes

• If we declare t within the loop it will be redeclared for each pass in the loop, does this change something in term of pure performance? Commented Apr 19, 2019 at 16:11
• Generally, declaring variables with the minimal possible scope allows the compiler to make better decisions regarding register allocation. However with code as small and simple as yours, it probably doesn't make a huge difference with modern compilers. Commented Apr 19, 2019 at 16:14
• OK, I thought there was some specific assembly instruction executed when declaring a variable. I know this doesn't matter right here but I'm interested in optimization. Commented Apr 19, 2019 at 16:19
• The condition while (b) is a bad abbreviation. For anything other than a boolean or a stream I prefer the explicit form while (b != 0). Having this implicit type conversion is not helpful for human readers. Commented Apr 20, 2019 at 4:42
• @RolandIllig: I prefer it with the shorter syntax. Regardless of which one uses, it's helpful to understand that they are 100% equivalent. Commented Apr 20, 2019 at 9:17