4
\$\begingroup\$

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';
}
\$\endgroup\$
5
\$\begingroup\$

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';
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You posted two answers? Why not merge them :) \$\endgroup\$ – morbidCode Feb 14 '15 at 9:51
  • \$\begingroup\$ Because the two answers are mutually exclusive. \$\endgroup\$ – 200_success Feb 14 '15 at 9:51
3
\$\begingroup\$

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

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.