LCM of First N Natural Numbers 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?
 A: 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...
A: Let $p_k$ be the $k$-th prime.  Let $n$ be the largest natural number such that $p_n\le N$. Then the LCM of the first $N$ natural numbers is given by
$$\prod_{k=1}^n p_k^{\,\lfloor \ln N / \ln p_k\rfloor}.$$
A: After just a quick thought I think it might look something like this:
For $n \in \mathbb{N}$
$$
LCM(1,2,\ldots, n) = p_1^\frac{k_1}{p_1} \cdot p_2^\frac{k_2}{p_2} \cdots p_i^\frac{k_i}{p_i},
$$
where $p_i$ are prime numbers smaller or equal than $n$. And $k_i$ is the biggest integer smaller or equal than $n$ that is divisible by $p_i$. 
But I might be wrong.
A: Yes, I was going to say people were getting confused between your usage of greatest common $D$ivisor vs $D$enominator. You can check out sequence A003418 at the Online Encyclopedia of Integer Sequences. They provide several formulas, none of which are explicit though. They also have a list of them for $N\le 500$
A: The (second) Chebyshev function gives the natural logarithm of the least common multiple of the first n natural numbers:
https://en.wikipedia.org/wiki/Chebyshev_function
A: If you don't want to assume having or constructing list if primes, you can just recursively apply the two argument LCM, resulting in something that is likely a bit worse than $O(n \cdot log n)$ time. You can likely improve to close to $O(n \cdot log n)$ by replacing the linear application with divide and conquer:
Assuming $f(n) = LCM(1, 2, ... n)$
Then define $f\prime(m,n)$ so that $f(n) = f\prime(1, n)$
Then

*

*If $m = n$ then $f\prime(m,n) = n$

*If $m < n$ then $f\prime(m,n) = LCM(f\prime(m, \lfloor{(m+n)/2}\rfloor), f\prime(\lfloor{(m+n)/2}\rfloor+1,n))$
This does the same $n-1$ LCM evaluations as the linear solution but it should do that majority of them with significant smaller numbers which should speed things up a bit. On the other hand it results in $log_2(n)$ values having to be held at some point in time as a trade off. If you are willing to accept an $O(n)$ space cost to do that, then it might be even better to do:

*

*allocate a min queue,

*populate it with 1 to $n$

*pop and LCM the smallest two values

*re-insert the result

*continue at step 3 until only one value remains.

