Project Euler #5 in C++

Question

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

Answer 1

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

• o2640110: 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?
• Edward: 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.
• o2640110: 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.
• Roland Illig: 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.
• Edward: @RolandIllig: I prefer it with the shorter syntax. Regardless of which one uses, it's helpful to understand that they are 100% equivalent.