Is there an efficient way to calculate the least common multiple of the first n natural numbers? For example, suppose n = 3. Then the lcm of 1, 2, and 3 is 6. Is there an efficient way to do this for arbitrary n that is more efficient than the naive approach?
LCM of First N Natural Numbers – Divisibility
divisibility
Best Answer
I don't know if you would call this efficient, but one simple way to calculate it is the following:
Let $f(n)=\text{LCM} \{1,2,3.., n \}$. Then
$$f(n+1)=\left\{ \begin{array}{l c} f(n) \cdot p & \mbox{if $\ n+1=p^k$} \\ f(n) & \mbox{otherwise} \\ \end{array} \right.$$
This is a simple recursive formula, which tells you that all you have to do is check if the integer is a power of primes. The closed forms from many answers are actually better answers, the problem is that for large $n$ you'd need to have the lists of all primes up to $n$, while this formula tests the integers one at a time (but you hit the factorization problem).
If $n$ is small the closed form is by far the fastest, and for large $n$ both ways are extremely long. This recursive approach might be a little faster when $n$ is big but not too big...