3
$\begingroup$

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay).


Example: Give $3$ integers $1, 2, 4$ and $k = 2$; output: $2$ ($\gcd(2, 4) = 2$)

Could this problem be solved efficiently ? I am currently using randomized pruning search algorithm to find such value.

Edit: Since brute-force solution can have some overlap calculations, I am thinking about dynamic programming solution but I got stuck

$\endgroup$
  • $\begingroup$ This may help, but I'm not sure: if you write the prime factorization of each number, the GCD of $k$ numbers will be the product of the primes [with multiplicity] they have in common. $\endgroup$ – angryavian Aug 9 '14 at 15:05
1
$\begingroup$

there is no efficient solution. it reduces to the set cover problem, which is NP complete

so basically, you ask the question, "is it possible to come up with K numbers from this set such that their GCD is at least X" and then find the largest X for which this statement evaluates to true

essentially you are asking whether it is possible to choose some K sets (the factorizations of your list of numbers), such that the union of those sets contains every element in some other target set (the factorization of X)

$\endgroup$

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.