After Dementia 2020 became unrated because of this problem, I became very curious about it. Let p be the quantity of primes before n including. The answer is n + p - 4 only if p is number in a power of 2 and p > 4.
Before a strategy, by saying ELEMENTS, I mean only primes in their MAX POWER(e.g. for 19 it’s 9, 16, 5, 7, 11, 13, 17, 19(3^2 = 9 and 2^4 = 16)). The strategy is the following: make p / 2 pairs choosing any 2 elements for the pair and using LCM function(they will always have different LCMs). Now the quantity of unique elements is p / 2.
Next step: now make p / 4 groups applying LCM to the each group of 2 unique elements spending one step and replacing two elements by their LCM, note that this LCM will be different in each group but inside that group all elements will be replaced by their only one local LCM. Now we have p / 4 unique elements.
Repeat this step, until you get 2 unique elements.
For example, case n = 19:
9 16 5 7 11 13 17 19
9 16 5 7 11 13 323 323 (1)
9 16 5 7 143 143 323 323 (2)
9 16 35 35 143 143 323 323 (3)
144 144 35 35 143 143 323 323 (4)
Now make p / 4 groups(144 144 35 35 and 143 143 323 323 for example)
Apply LCM function
144 5040 5040 35 143 143 323 323 (5)
5040 5040 5040 5040 143 143 323 323 (6)
And for the last group
5040 5040 5040 5040 143 46189 46189 323 (7)
5040 5040 5040 5040 46189 46189 46189 46189 (8)
Now we can achive final LCM in 4 steps(final LCM is 232792560)
5040 5040 5040 232792560 232792560 46189 46189 46189 (9)
5040 5040 5040 232792560 232792560 46189 46189 46189 (10)
5040 232792560 232792560 232792560 232792560 232792560 232792560 46189 (11)
232792560 232792560 232792560 232792560 232792560 232792560 232792560 232792560 (12)
We used 8 elements in array[1, 2 … n - 1, n] and make them equal to our final LCM in 12 seconds.
Now we need to replace other 19 - 8 == 11 elements in 11 seconds and the answer is 11 + 12 = 23. It’s faster for 19 than n + p - 3 solution(19 + 8 - 3 = 24) exactly by 1 second and solution is n + p - 4.