# Project Euler - 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';
}


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

• 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

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