suppose u have the array : a[ ] = { 4,6,8,9,12 }

Now, starting with the first element 4, we will find out all of its prime factors which in this case is 2 only.

Now, we will create a temp array for checking if any prime factor has came before or not.

so , in this case temp[2]=0, so we will assign temp[2]= 1, where 1 is the index of 4.

Now , moving to the next element , we have 6, whose prime factors are 2 and 3.

As , 2 has occured before so we will put ans[2]=max(ans[2],temp[2]) , where ans[2] is the current answer of the element having index 2.

Now , we will update the temp[2]=2, where 2 is the index of 6.

Similarly, temp[3]=2

Similarly , check for next element upto the rightmost element.

After doing that , use the same process from step 1 from right to left and u will get the answer.