Maximum coprime subset

Question

Given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.

Example : Let N=5 and array be [2 3 2 3 2] then answer is 2

Explanation : The largest subset would be taking one of A[0], A[1], A[2] and taking one of A[3], A[4].

N can be at max 50. How to approach this question ?

Answer 1

Since for all i you know that 1 ≤ Ai ≤ 50, you can first filter the input, after which bruteforcing becomes feasible.

You can always select all primes for your subset, because each prime is at least as good as any multiple of that prime (for a given prime p, if an integer x is coprime with some k * x, then it is also coprime with p). After that you can remove all multiples of the selected primes, because they cannot be in the result.

For even more filtering, consider the following: every integer can be uniquely written as a product of primes, for instance:

 2 = 21
 6 = 2131
40 = 2351

For an integer x, let's write x0 for the corresponding integer with all prime factors having power 1. For example, if x = 40 (2351), then x0 = 10 (2151). We do not need to consider primes with power >1, because for every integer y holds that if x and y are coprime, then so are x0 and y. Since you are only interested in the size of the subset, you can replace each x by x0.

There are only 14 numbers below 50 that are no prime and have no prime factor with power >1.

6, 10, 14, 15, 21, 22, 26, 30, 33, 34, 35, 38, 39, 42

The reduced numbers x0 are members of this set. Since there are so few, you can simply bruteforce in order to find the biggest subset.

Answer 2

There's a lot you can do to optimize this brute force solution:

Generate all strings of length 2^N containing 0 and 1 and for each of them, consider the subset of numbers from your array corresponding to the positions of ones. So for:

10010

You'd consider:

2 3

This can be valid according to your restrictions or it might not be. If it's not valid, then any other numbers you add to it will also lead to an invalid set.

So one thing you can optimize is this: whenever you generate a 1 in your string, check if the number it corresponds to is coprime with the numbers corresponding to the previously generated ones. If yes, stop generating and backtrack.

Another thing that might help is sorting your array: This might help put non-coprimes closer together (especially if your range of values is small), thus helping you cut your searches short faster.

To convince yourself that what I said above can work, realize that the primes below 50 are:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 49

So only 16. This means that this is the maximum length of such a subset that you are ever going to find, so there's no point trying to find a longer one. The first optimization will help limit generated subsets to length at most 16.

Next, for any pair x, y in your original array such that x mod y = 0, you can drop x from your array: this works because if x is a multiple of y, it will have all of y's divisors and maybe more. So if there is a solution containing x, that solution will not be extendable using y, but it will be valid if we replace x with y.