May be there is a better way, but I would put the two numbers with the best accordance in the set of prime factors in one array and all "show stoppers" to the second. Example:
8: 2*2*2
12: 2*2 *3
78: 2 *3 *13
125: 5*5*5
8 and 12 have factor 2*2 in common, but 12 and 78 have 2*3 which is a bit better. So the first array is {12, 78} with GCD = 6 and the second {8, 125} with GCD = 1.
(BTW, those who need a brush up in fractions, get 125/12 - 78/8 with no help but pen and paper.)