I have to take input in an array(no. of elements in array <=10^5).
For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in the set have gcd > 1.
In the example:- {3,9,45,27,81} is such a set.It's order is=5, hence 5 is my ans.
Note that {2,4,16} also has pairwise gcd's >1 but it is not maximal (5>3).
What I did:-
I tried to find every possible set which meets the condition and then see the maximum order but that doesn't seem to work(works in some cases, but fails in majority).
The input numbers are <=10^7 so this needs to be fast.