Project Euler Problem 5: Smallest Multiple

2026-03-03 13:45

The Problem

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?

First Thoughts

So “evenly divisible” just means divisible with no remainder, which immediately makes you think about the modulo operator. My first instinct was to brute force it: loop over every number starting from 1, check if it’s divisible by all numbers from 1 to 20 using modulo, and return the first one that passes. That works in theory but it’s painfully slow. You’d be checking millions of candidates.

Then I thought about it more mathematically. What we’re actually looking for is the Least Common Multiple of all numbers from 1 to 20. The smallest number divisible by all of them is their LCM by definition. So we don’t need to search at all, we just need to compute it directly.

The GCD/LCM Connection

There’s a useful identity:

gcd(a, b) * lcm(a, b) = a * b

Which means:

lcm(a, b) = (a / gcd(a, b)) * b

This is how you compute LCM efficiently without doing anything fancy. And LCM is associative, so:

lcm(a, b, c) = lcm(lcm(a, b), c)

That means you can fold LCM across a sequence of numbers one at a time, carrying a running result. This is the core idea of the solution.

Writing the Loop

The structure is simple: keep a running result and update it each iteration.

long long result = 1;
for (int i = 1; i <= 20; i++) {
    result = std::lcm(result, i);
}

A few things I got wrong on the way here that are worth noting:

Initializing to 0 breaks everything

lcm(0, x) = 0 for any x. So if you initialize result = 0, it stays 0 forever no matter what the loop does. The correct neutral starting value is 1, because lcm(1, x) = x always. It’s the identity element for LCM, same as how 0 is the identity for addition.

Starting the loop at i=0 also breaks everything

For the same reason. The first iteration would compute lcm(1, 0) = 0 and you’re back to the same problem. Start at i = 1.

LCM is not the same as factorial

I initially thought maybe the answer was related to 20! or something like that. But 20! is around 2.4 quintillion, which is enormous. LCM(1..20) is much smaller because LCM accounts for shared prime factors. If two numbers share a factor, you don’t count it twice. Factorial just multiplies everything blindly.

Use long long

The answer is too big for a regular int. Always use long long when you expect large numbers in these problems.

The Final Code

#include <iostream>
#include <numeric>

int main() {
    long long result = 1;
    for (int i = 1; i <= 20; i++) {
        result = std::lcm(result, i);
    }
    std::cout << result << std::endl;
    return 0;
}

Compile with:

g++ -std=c++17 -o smallest_multiple smallest_multiple.cpp

Note that std::lcm requires C++17 and you need to call it with the std:: prefix explicitly, otherwise the compiler will complain about an undeclared identifier even though it suggests std::lcm itself in the error message.

[learn] [cpp] [euler] [math]