如果a与b可以互换，b与c可以互换，那么意味着a,b,c三个数的位置可以任意流动。我们很容易想到，应该将所有gcd不为1的“数对”都union在一起组成一个group，这些数彼此之间的顺序我们就可以任意调整。
我们将原数组nums排序后得到一个期望的nums1，那么对于任意位置i，我们要判断nums[i]和nums1[i]这两个数是否在同一个group。如果是的话，说明我们可以在原数组里，将nums1[i]这个数字调动到i这个位置上来。例如:
nums: 4 3 2 8
- - -
nums1: 2 3 4 8
对于Index=0的位置，原来的值是4，我们希望排序的值是2. 而我们通过union find处理数组后，可以知道4,2,8就是同一组的。所以必然可以把2移到index=0的位置。同理，我们逐位检查FindFather(nums[i])==FindFather(nums1[i])，都成立的话就可以返回true。
对于Union Find的策略，我们显然不会比较每一对数字查看gcd，那样是o(N^2)的时间消耗。比较合理的方法是对每个数因式分解，将含有相同质因数的元素都union到一起。这样就等价于把所有gcd不为1的“数对”都union在一起。
因式分解的方法，可以提前将所有小于100000的质因数都计算出来（用埃氏筛，时间复杂度是NloglogN），这样再用所有质因数去除每个nums[i]，看该元素能与哪些质因数组Union在一起。
Update: 本题的因式分解部分可以进一步优化。我们可以只提前计算所有小于sqrt(100000)的质因数。当我们用所有的质因数都除完nums[i]之后，如果剩下的元素依然大于1，说明剩下的数值必然就是一个质因数。