I think it would be NP complete. One NP complete problem is to determine if a graph has an Vertex Cover of size $k$: given graph with m vertices and e edges is there a set of k vertices including at least on endpoint of each edge. TO ? To encode this in your problem, assign a unique prime $p_i$ to each edge $e_i$, let $P=\prod p_i$, and assign to each vertex $v$ the integer $\frac{P}{\prod_{v \in e_i}p_i}$. Then the $\gcd$ is $1$ and a subset with that $\gcd$ is a vertex cover of the edges.
I am sure that there are other more elegant covering or satisfiability problems but that will do.
I'd say leave the issue of factoring out of it by assuming that the factorizations are all known. Of course then you could replace each integer $2^a3^b5^c\cdots$ by a vector $[a,b,c,\cdots]$ and look at the entry-wise minimum over the whole set and over various subsets.
