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';
}

• lightning_missile: You posted two answers? Why not merge them :)
• 200_success: Because the two answers are mutually exclusive.

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;
}