<p>You are given an integer array <code>nums</code>, and you can perform the following operation <strong>any</strong> number of times on <code>nums</code>:</p>

<ul>
	<li>Swap the positions of two elements <code>nums[i]</code> and <code>nums[j]</code> if <code>gcd(nums[i], nums[j]) &gt; 1</code> where <code>gcd(nums[i], nums[j])</code> is the <strong>greatest common divisor</strong> of <code>nums[i]</code> and <code>nums[j]</code>.</li>
</ul>

<p>Return <code>true</code> <em>if it is possible to sort </em><code>nums</code><em> in <strong>non-decreasing</strong> order using the above swap method, or </em><code>false</code><em> otherwise.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,21,3]
<strong>Output:</strong> true
<strong>Explanation:</strong> We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [<u><strong>21</strong></u>,<u><strong>7</strong></u>,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [<u><strong>3</strong></u>,7,<u><strong>21</strong></u>]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to sort the array because 5 cannot be swapped with any other element.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,5,9,3,15]
<strong>Output:</strong> true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [<u><strong>15</strong></u>,5,9,3,<u><strong>10</strong></u>]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [<u><strong>3</strong></u>,5,9,<u><strong>15</strong></u>,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,<u><strong>10</strong></u>,<u><strong>15</strong></u>]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>2 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

from typing import  List


import math
is_prime = []
primes = []
class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        global primes
        global is_prime

        if len(primes) == 0:
            until = 320 # 100001
            is_prime = [True for i in range(until)]
            is_prime[0] = False
            is_prime[1] = False
            primes=[2]
            for i in range(4, until, 2):
                is_prime[i] = False
            for i in range(3, until, 2):
                if is_prime[i]:
                    primes.append(i)
                    for j in range(i * i, until, i * 2):
                        is_prime[j] = False


        a = nums
        b = [i for i in a]
        parent = [-1 for _ in range(len(a))]
        q = []
        for p in primes:
            any_parent = None
            divisible_by_this = []
            for i in range(len(a)):
                if a[i]%p==0:
                    while a[i]%p==0:
                        a[i]//=p
                    divisible_by_this.append(i)
                    if parent[i]!=-1:
                        any_parent=parent[i]


            if len(divisible_by_this)==0:
                continue
            if any_parent == None:
                any_parent = divisible_by_this[0]

            for i in divisible_by_this:
                parent[i]=any_parent

            for i in range(len(parent)):
                if parent[i]==-1:
                    continue

                t = parent[i]
                while t!=parent[t]:
                    t = parent[t]
                parent[i]=t


        other_primes = set()

        parents_of_other_primes = {}
        for i in range(len(a)):
            if a[i]>1:
                if parent[i]!=-1:
                    if a[i] in parents_of_other_primes and  parent[i]!=parents_of_other_primes[a[i]]:
                        x = parent[i]
                        y = parent[i]!=parents_of_other_primes[a[i]]
                        while x!=parent[x]:
                            x=parent[x]
                        while y!=parent[y]:
                            y = parent[y]
                        parent[x]=y
                        parent[i]=y
                        parents_of_other_primes[a[i]]=parent[i]

                        #print("heb")
                    else:
                        parents_of_other_primes[a[i]]=parent[i]
                other_primes.add(a[i])
        for i in range(len(a)):
            t = parent[i]
            while t != parent[t]:
                t = parent[t]

            parent[i] = t
        for i in range(len(a)):
            if a[i]>1:
                if a[i] in parents_of_other_primes:
                    parent[i]=parents_of_other_primes[a[i]]
                else:
                    parent[i]=i

        d = {}
        for i in range(len(a)):
            if parent[i] not in d:
                d[parent[i]]=[]
            d[parent[i]].append(b[i])

        index = {}
        for key in d.keys():
            d[key]=sorted(d[key])
            index[key] = 0

        for i in range(len(a)):
            a[i] =d[parent[i]][index[parent[i]]]
            index[parent[i]]+=1




        for i in range(1,len(a)):
            if a[i]<a[i-1]:
                return False
        return True
2744