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!