There is a very intuitive way to formulate the answer sequence.
We can start by filling all the primes <= n with ‘1’. This works because prime numbers have no other factor than ‘1’ and themselves. Hence giving them a value ‘1’ is appropriate.
So how we fill composite numbers? The answer is simple we fill them based on their largest factor. Why? This is because since we have already filled all the numbers <= current number, hence the only factor that makes sense is the largest factor of the current number. What value to we assign to this number? We assign val[largest factor]+1, since we can’t repeat. Now we can do this for every number from [2, N], and finally assign the value val[1] = max(2, N) + 1.
A quick way to find largest factor is to find the lowest prime factor and divide the number by it, for example lpf[46] = 2 and it’s largest factor is 23 [46 / 2].
This construction always works and is very intuitive.