up vote 2 down vote favorite

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';
}
share|improve this question
up vote 3 down vote accepted

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';
}
share|improve this answer
1  
You posted two answers? Why not merge them :) – morbidCode Feb 14 '15 at 9:51
    
Because the two answers are mutually exclusive. – 200_success♦ Feb 14 '15 at 9:51
up vote 2 down vote

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;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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