# Least common multiple of a list of numbers

I'm trying to learn computer science by doing some challenges. One is the following.

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?

Let's generalize the problem from $$1$$ to $$n$$.

I thought of a loop between $$n$$ and $$n/2$$ as everything above $$n/2$$ is a multiple of something between $$1$$ and $$n/2$$. At each iteration, the result is the least common multiple of the loop variable and the precedent result (at the beginning the result is 1).

If I am correct, the complexity of this should be $$\mathcal{O}(n/2)$$. Am I right?

Is there any more efficient algorithms to solve this problem? If so witch one and what is their complexity?

• You will indeed have $O(n/2)$ loop iterations, however at each one, you need to find the GCD of two numbers, which is not constant time and thus your overall runtime will be be greater than $O(n/2)$ How are you calculating GCD? Commented Apr 20, 2019 at 14:11
• @BryceKille I'm using Euclid's algorithm with modulo. Commented Apr 20, 2019 at 15:23
• Ok. So at every step $i$, you are computing $GCD(i, prec)$ where $prec$ is the precedent result, which is certainly greater than $i$. Therefore at every step, you have $O(\log i)$ complexity. Even if you only do half of the loops, this will still end up being $O(n\log n)$ then. Commented Apr 20, 2019 at 15:45

Suppose that we are interested in the LCM of all numbers from $$1$$ to $$n$$. It is not hard to check that the answer is the product of $$p^{k_p}$$ for all primes $$p \leq n$$, where $$k_p$$ is the largest integer such that $$p^{k_p} \leq n$$. For example, the primes at most 10 are $$2,3,5,7$$, and so the answer is $$2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520.$$ Similarly, the primes at most 20 are $$2,3,5,7,11,13,17,19$$, and so the answer is $$2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19.$$
• Note that the output will be quite large, $\Theta(n)$ bits. Commented Apr 20, 2019 at 15:48