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?

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.

