1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ (Would make a nice question on SO (,GCDs, spaces and abbreviations corrected). The source may be recognised immediately over there.) $\endgroup$ – greybeard Dec 3 '16 at 10:16
  • $\begingroup$ Is this, by any chance, taken from a programming competition? $\endgroup$ – Yuval Filmus Dec 3 '16 at 10:43
  • 1
    $\begingroup$ 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 -_- $\endgroup$ – user249117 Dec 3 '16 at 16:54
  • $\begingroup$ There are more recent questions here from that contest. $\endgroup$ – gnasher729 Dec 3 '16 at 17:13
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Dec 3 '16 at 12:05
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 3 '16 at 12:10
  • $\begingroup$ @quicksort If only i could understand it how to use this in my problem and code it :-( $\endgroup$ – Ravi kumar Dec 3 '16 at 12:40
  • 1
    $\begingroup$ @YuvalFilmus: Interesting that here we have a problem that is in general NP-complete but with these two restrictions it is hopefully not particularly hard; there are other problems where you don't have the slightest hope to solve them with much stricter restrictions. $\endgroup$ – gnasher729 Dec 3 '16 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.