# Choose a k-subset such that its elements 's gcd is maximal

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

• 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. – angryavian Aug 9 '14 at 15:05