Algorithm for finding maximum mutually coprime subset of a multiset of integers
Your problem is equivalent in complexity to the maximum set packing problem.  Unfortunately, maximum set packing is NP-hard.  Therefore, you'll need to use one of the methods in Dealing with intractability: NP-complete problems.



Here's the gist of the equivalence.  Each integer in your set A corresponds to a set of its prime factors; now you're looking for a maximum-size collection of those sets that are pairwise disjoint.  That's exactly maximum set packing.  This is only the gist of the idea; this reduction doesn't quite work, because as you noticed, factoring each element of A can take quite a bit of time (there's no known polynomial-time algorithm for factoring).

It's possible to fix up the reduction as follows.  Given an instance of your problem, factor A into a coprime base.  A coprime base is a list of integers that are pairwise co-prime (no two elements in the coprime base any common factor), and where every number in A can be factored into a product of elements of the coprime base.  For instance, a coprime base for A = {30, 105, 126} would be {5, 6, 21}.  Note that the elements of the coprime base do not need to be prime.  There are efficient algorithms for finding a coprime base for A.  Now, associate to each number x in A the set of elements of the coprime base that are divisors of x.  Then you have an instance of the maximum set packing problem.

(Conversely, given an instance of the maximum set packing problem, you can convert it into an instance of your problem, by simply treating the universe for the set packing instance to be the prime numbers.)



So given that you basically have an instance of maximum set packing, what should you do?  Well, maximum set packing has been well-studied, so you can use the literature on that problem.  Here are some candidate approaches:

ILP: It's easy to formulate the maximum set packing problem as an instance of integer linear programming.  You have a zero-or-one variable $x_i$ for each integer $i$ in A, with the idea that $x_i=1$ means that $i$ is included in the output list.  You add a constraint $x_i+x_j \le 1$ for every pair of numbers $i,j$ that have a common factor.  Then, you try to maximize the objective function $\sum_{i \in A} x_i$.  Feed this to an off-the-shelf integer linear programming solver, and it will give you the best solution it could find.

If you want something simple to implement and optimal, I suspect the ILP-based algorithm is your best bet.  It'll be easy to implement.  There's no guarantee that it'll be efficient -- it's an NP-hard problem, after all -- but it might work well enough in practice if the problems sizes are small enough.

Heuristics: You can use any of the known heuristics for set packing.  See, e.g., https://en.wikipedia.org/wiki/Set_packing#Heuristics, or search the research literature.

Approximation algorithms: Wikipedia says that it is known how to approximate maximum set packing to within a factor $k/2$, if $k$ is the size of the largest set.  (In other words, $k$ is the maximum number of elements of the coprime base that can divide any single element of A.)  If the numbers in A aren't too large, then $k$ will be relatively small, so this approximation algorithm might be reasonably effective.  Wikipedia doesn't say what the algorithm is, so you'll have to do some research in the literature.