If you write down all numbers from 1 to n, you will notice that only the highest multiple of primes contribute to the LCM. Let’s say that there are p such numbers. It is optimal to convert these to the LCM first rather than the other numbers. In p-1 operations, you can make the last and second-to-last numbers equal to the LCM. Then we can make the other n-p+p-2 = n-2 numbers equal to the LCM. We also used p-1 operations to make the last number equal. So
the formula is p-1+n-2 = n+p-3
The edge cases are n = 1, \ 2.
9 Likes