There are n numbers. Find the maximal set of pairwise NON coprime numbers I have to take input in an array(no. of elements in array &lt;=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 &lt;=10^7 so this needs to be fast.
Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge $uv$ of $G'$ with a prime number $p_{uv}$ such that for each pair of edges $uv, wx \in E$ it holds that $p_{uv} \neq p_{wx}$
Now, label each $v \in V$ with $$ \prod_{u \in Adj(v)} p_{uv}\,.$$

Now, take the set of the labels. A subset of it is the maximum set of non-parwise coprime numbers if and only if it is a maximum clique in $G'$, if and only if it is the maximum independent set of $G$.