# Maximum Pairwise GCD from an even subsequence of an array

I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to obtain the maximum pairwise gcd from a subsequence of the array given that the size of the subsequence must not exceed 2*X.

So for example, my array is [5, 7, 10, 8, 3, 4] and X is 2: the answer would be 9 since GCD(5, 10) + GCD(8, 4) = 9

The only approach I've been able to come up with was: At each step I'll find the maximum pairwise GCD of the numbers and then remove the 2 numbers from the array. Will keep adding it to a sum(which I have to output), under the constraints that I dont take in more than 2*X numbers.

But this approach is too slow. If someone can suggest a faster approach, it would be great. Thanks!

• This is not clear at all. You say you are trying to find a subsequence, but your final answer is $9$, which is not a subsequence. If you meant the subsequence $\{4,5,8,10\}$ then it is not clear how you came up with the number $9$. And...what is the source of this problem? It looks like the sort of thing that shows up in programming challenges...is it? – lulu Jul 28 at 12:26
• @lulu yes it is. Sorry for the poor phrasing. I'll correct it. – Karan Singh Jul 28 at 12:28
• And please include the link to the programming contest. – lulu Jul 28 at 12:28
• do you know not to pair up primes or prime powers with different bases as a pair unless forced ? – Roddy MacPhee Jul 31 at 21:01