Project Euler - Smallest multiple Here's Problem 5 - Smallest multiple


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?


How can I improve this code? How to make it faster? Is there a better/faster solution?

#include &lt;iostream&gt;

bool calculate(int number, int n) {
    if (n == 0) {
        return true;
    }
    return (number % n != 0) ? false : calculate(number,n-1);
}

int main() {
    int number = 20;
    int result = number;
    while (!calculate(result, number)) {
        result += number;
    }
    std::cout &lt;&lt; result &lt;&lt; '\n';
}
You arrive at the answer by counting 20 at a time.  That's 11639628 iterations of the main loop — and many recursive calls to calculate().

A more efficient and satisfying approach would be to use the Euclidean Algorithm to compute LCMs.

Note that an int is not guaranteed to be large enough to hold the result.  I suggest using long everywhere.

#include &lt;iostream&gt;

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

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

int main() {
    long result = 20;
    for (long number = result - 1; number &gt; 1; --number) {
        result = lcm(result, number);
    }
    std::cout &lt;&lt; result &lt;&lt; '\n';
}