Project Euler - Smallest multiple

Question

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 <iostream>

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 << result << '\n';
}

Answer 1

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 <iostream>

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 > 1; --number) {
        result = lcm(result, number);
    }
    std::cout << result << '\n';
}

Answer 2

calculate() is not at all an informative name. My suggestion for the name would be isMultipleOfRange(). Personally, I find it easier to understand if written non-recursively, but that's a matter of opinion.

bool isMultipleOfRange(int number, int n) {
    while (n > 0) {
        if (number % n-- != 0) return false;
    }
    return true;
}