Problem 5 - Smallest Multiple

Ella, Sri Lanka - 9 Arches Bridge - April 30th, 2025

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?

https://projecteuler.net/problem=5

Development

To start out, we write a simple program to test numbers from 1 to 11, 1 to 12, and so forth to test runtime feasibility.

e.g.

n <- 2520
x1 <- 1
x2 <- 11
while (TRUE) {
  if (all(n %% x1:x2 == 0)) {
    return(n)
  }
  n <- n + 1
}

The runtime begins to become non-trivial at x2=19.

We notice that all answers from x2={11,12,..,18} are multiples of 2520.

Thus, we can increase n incrementally by 2520 instead of incrementally by 1.

R

Answer 1

Code

#' @param n Starting number
#' @param inc increment to increase by
#' @param x1 Lowest factor
#' @param x2 Highest factor
n_x1_to_x2 <- function(n, inc = 1, x1 = 1, x2 = 10) {
  while (TRUE) {
    if (all(n %% x1:x2 == 0)) {
      return(n)
    }
    n <- n + inc
  }
}

tic()
n_x1_to_x2(2520, 2520, 1, 20)
toc()

[1] 232792560
0.077 sec elapsed

Answer 2 - No(Low) Code

We don’t need much code here.

We need to compute the LCM (Least Common Multiple) of 2520 & a number that is the product of 1-20 using prime factorization.

The LCM is the product of the highest power of each prime. Prime factorization of 1-10 do not have higher powers.

Multiple	Prime Factorization
11	11
12	2^2 * 3
13	13
14	2 * 7
15	3 * 5
16	2^4
17	17
18	2 * 3^2
19	19
20	2^2 * 5

\(LCM = 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19\)

Code

2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

[1] 232792560

Answer 3

LCM & Prime Factorization, just code:

Code

l_pf <- primes::prime_factors(1:20)
l_pf_c <- l_pf |> lapply(table)
p <- unique(unlist(l_pf))
d_lcm <- data.frame(p = p)
l_lcm <- c()
for (p_i in p) {
  i_p <- lapply(l_pf, function(i) i == p_i) |> lapply(sum) |> unlist() |> which.max()
  l_lcm[[as.character(p_i)]] <- l_pf_c[[i_p]][[1]]
}
d_lcm$y <- l_lcm
prod(d_lcm$p ^ unlist(d_lcm$y))

[1] 232792560

Python

Answer 1

Reuse

Citation

For attribution, please cite this work as:

Clemson, Vincent. 2026. “Problem 5 - Smallest Multiple.” January 17, 2026. https://prncevince.xyz/euler/problem/0005.html.