You are given an integer array nums, and you can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Example 1:

Input: nums = [7,21,3]

Output: true

class Solution {

public boolean gcdSort(int[] nums) {

for(int x: nums) {

int y = x;

for(int p=2; UF[y]==0 && p*p<=y; ++p) {

if (y % p == 0) {

union(x, p);

while(y % p == 0) y /= p;

}

}

if (y!=1) union(x, y);

}

int[] copy = nums.clone();

Arrays.sort(copy);

for(int i=0; i<nums.length; i++) {

if (find(nums[i])!=find(copy[i])) return false;

}

return true;

}

private int[] UF = new int[100001];

private int find(int x) {

if (UF[x]==0) return UF[x]=x;

return UF[x]==x? x: (UF[x]=find(UF[x]));

}

private void union(int x, int y) {

UF[find(x)] = UF[find(y)];

}

}