Problem Page : KIRLAB

My solution : Solution WA

It is asking to find out the longest subsequence in array such that every adjacent pair of the subsequence has GCD>1, or we can say every adjacent pair shares some common prime factor.

Suppose We are given array A[ ].

I made an array B[ ] of 10^7 size and initialized with all zeroes.

Then I traverse the given array A[ ], and for each element A[i], I increment B[j] for all prime factors j of A[i] and choose the max of the updated $B[j]$s and then update all these $B[j]$s with this chosen max value. In this way, max of array B[] now tells the max length of subsequence found till now.

This solution is giving WA. Please tell me what is wrong in my solution.

Thanks