3
\$\begingroup\$

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";
}
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – o2640110 Apr 19 at 16:11
  • \$\begingroup\$ 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. \$\endgroup\$ – Edward Apr 19 at 16:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – o2640110 Apr 19 at 16:19
  • \$\begingroup\$ 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. \$\endgroup\$ – Roland Illig Apr 20 at 4:42
  • 1
    \$\begingroup\$ @RolandIllig: I prefer it with the shorter syntax. Regardless of which one uses, it's helpful to understand that they are 100% equivalent. \$\endgroup\$ – Edward Apr 20 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.