There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to lift the maximum number of boxes possible.
But there is a condition that must be fulfilled for the lifted boxes. For every pair of the lifted boxes, the $GCD$ of the weights of those should be greater than $1$.
Eg 1: N=7 Weights - 13 2 8 6 3 1 9 Answer - 5
We can lift the boxes $2, 3, 4, 5, 7$ in this order. These boxes have following weight- $2, 8, 6, 3,9$ respectively. Note that $gcd(2, 8), gcd(8, 6), gcd(6, 3),gcd(3, 9)$ $>1$.
Eg 2 N=6 Weight - 1 3 3 5 5 1 Answer- 2
We can lift boxes numbered $2, 3$ as $gcd(3, 3) = 3 > 1$.
There is one more possible solution: We can lift boxes numbered $4, 5$ as $gcd(5, 5) = 3 > 1$.
I thought of a naive solution to check $GCD$ of every successive pair and eliminating that box with whom $GCD$ of next box will be equal to $1$. But this will be very time consuming and not efficient at all. It's time complexity will be quadratic or polynomial.
Now I can't figure out any better and efficient solution/algorithm to find the answer. Any help will be appreciated. Also I would like to keep the time complexity less than quadratic time like maybe $O(N*LOGN)$.