GCD Sort of an Array

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

Inputnums = [7,21,3]

Outputtrue

We can sort [7, 21, 3] by swapping 7 with 21, then swapping 21 with 3, since each swap has gcd greater than 1.

Example 2

Inputnums = [5,2,6,2]

Outputfalse

It is impossible to sort the array because 5 cannot be swapped with any other element.

Constraints