### gcdSort 
import math
from math import gcd
from collections import defaultdict
from typing import *
def f_gold(nums: List[int]) -> bool:
    n = 10**5 + 10
    p = list(range(n))
    f = defaultdict(list)
    mx = max(nums)
    for i in range(2, mx + 1):
        if f[i]:
            continue
        for j in range(i, mx + 1, i):
            f[j].append(i)
    def find(x):
        if p[x] != x:
            p[x] = find(p[x])
        return p[x]
    for i in nums:
        for j in f[i]:
            p[find(i)] = find(j)
    s = sorted(nums)
    for i, num in enumerate(nums):
        if s[i] != num and find(num) != find(s[i]):
            return False
    return True