Finding the largest subset of factors of a number whose product is the number itself

I would suggest you try a greedy approach. I haven't developed it into an algorithm, but it is a thought. If you factor $x=p^aq^br^c \ldots$ into prime powers, the answer will only depend on the multiset $\{a,b,c,\ldots \}$. The primes will not matter. The first factors to claim are the primes dividing $x$, specifically $p,q,r,\ldots$ The next cheapest factors are of the form $pq$ or $p^2$. You don't want to use the square for primes you don't have many of. Next try $p^2q$ where you consider primes with low exponents expensive and don't square them. This seems a problem that is very hard to program, but will be obvious to a human as long as the number of prime powers is not too large.