# 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 <=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.

• (Would make a nice question on SO (,GCDs, spaces and abbreviations corrected). The source may be recognised immediately over there.) Dec 3 '16 at 10:16
• Is this, by any chance, taken from a programming competition? Dec 3 '16 at 10:43
• The question is currently one of the 10 questions of December long challenge. codechef.com/DEC16/problems/KIRLAB And this guy mentioned in comments that this is not taken from any ongoing contest -_- Dec 3 '16 at 16:54
• There are more recent questions here from that contest. Dec 3 '16 at 17:13

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$.
• Welcome to the site! I took the liberty of editing your answer to remove the function $\phi$, since it seemed to me to just add a layer of indirection and complication to the answer. If you don't like my edit, click on the "edited whatever time ago" link above my avatar and use the rollback link to go back to your original version. Dec 3 '16 at 12:05
• The OP's variant isn't NP-complete: all the inputs are at most $10^7$, and there are at most $10^5$ of them. It can be solved in $O(1)$. The question is, what is the best constant that you can get. It's a practical rather than a theoretical question. Dec 3 '16 at 12:10