GCD Sort of an Array

Determine whether an array can be sorted using only swaps between elements whose gcd is >1 — equivalently, check if each number can be moved to its sorted position within connected components formed by edges between numbers that share a prime factor. This reduces to a connectivity/multiset check (e.g., via union-find over prime factors) to see if each component's values can be permuted to match the sorted array.