# Algorithm : Select maximum number of Boxes to lift from N boxes

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

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

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)$.

• You should mention that it is a problem from a recent programming contest. Competing with an answer received here would be cheating. – gnasher729 Dec 3 '16 at 17:15
• I'm voting to close this question as off-topic because it is part of a current contest. – David Richerby Dec 3 '16 at 19:29
• @DavidRicherby: Would it make sense to put the question on hold until the competition is over? And if that was done, would it be Ok to post an answer taken from the competition? – gnasher729 Dec 3 '16 at 22:32
• @gnasher729 Yes, I think it should be put on hold; I don't see any particular reason to keep it closed once the contest is over. We tend to prefer original answers to answers that are just quotations from some other source. It would probably be better to cite the competition answer in an answer that explained what was going on. – David Richerby Dec 3 '16 at 22:53