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 &lt;iostream&gt;

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 &gt; n/2; --i) {
        result = lcm(result, i);
    }
    std::cout &lt;&lt; "Result: " &lt;&lt; result &lt;&lt; "\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 &lt; 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