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