<p>You are given an integer array of unique positive integers <code>nums</code>. Consider the following graph:</p>

<ul>
	<li>There are <code>nums.length</code> nodes, labeled <code>nums[0]</code> to <code>nums[nums.length - 1]</code>,</li>
	<li>There is an undirected edge between <code>nums[i]</code> and <code>nums[j]</code> if <code>nums[i]</code> and <code>nums[j]</code> share a common factor greater than <code>1</code>.</li>
</ul>

<p>Return <em>the size of the largest connected component in the graph</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex1.png" style="width: 500px; height: 97px;" />
<pre>
<strong>Input:</strong> nums = [4,6,15,35]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex2.png" style="width: 500px; height: 85px;" />
<pre>
<strong>Input:</strong> nums = [20,50,9,63]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex3.png" style="width: 500px; height: 260px;" />
<pre>
<strong>Input:</strong> nums = [2,3,6,7,4,12,21,39]
<strong>Output:</strong> 8
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>nums</code> are <strong>unique</strong>.</li>
</ul>

class Solution:
    def __init__(self):
        self.p = {}
        self.rank = {}
        self.prime = []
        self.factor = {}

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        print('union: {}-{} -> {}-{}'.format(u, v, pu, pv))
        if pu == pv:
            return
        if self.rank[pu]>self.rank[pv]:
            self.p[pv] = pu
        else:
            self.p[pu] = pv
            if self.rank[pv] == self.rank[pu]:
                self.rank[pv] += 1

    def find(self, u):
        if self.p[u] == u:
            return u
        self.p[u] = self.find(self.p[u])
        return self.p[u]

    def genPrime(self, largest):
        bound = largest + 1
        sieve = [True]*(bound)
        for num in range(2, bound):
            if sieve[num]:
                i = 2
                while i*num < bound:
                    sieve[i*num] = False
                    i += 1
                sieve[num] = True
                self.prime.append(num)

    def initDSU(self, bound):
        for num in range(bound):
            self.p[num] = num
            self.rank[num] = 0
        
    def factorize(self, num):
        # m, i = num, 2
        # while i*i <= num:
        #     if num % i == 0:
        #         pNum = self.find(num)
        #         pI = self.find(i)
        #         if pNum != pI:
        #             self.union(pNum, pI)
        #         while num%i == 0:
        #             num = num // i
        #     i += 1
        print("num: ", num)
        m, i = num, 0
        while self.prime[i]**2 <= num:
            prime = self.prime[i]
            if num % prime == 0:
                pM = self.find(m)
                pPrime = self.find(prime)
                if pM != pPrime:
                    self.union(pM, pPrime)
                while num%prime == 0:
                    num = num // prime
            i += 1

        if num>1:
            print(".")
            pNum = self.find(num)
            pM = self.find(m)
            if pNum != pM:
                self.union(pNum, pM)
        print()

    def largestComponentSize(self, nums: List[int]) -> int:
        bound = 10**5 + 1
        self.genPrime(bound)
        self.initDSU(bound)

        for num in nums:
            self.factorize(num)

        print("result: ")
        ans, count = 1, {}
        for num in nums:
            root = self.find(num)
            print(num, root)
            count[root] = count.get(root, 0) + 1
            ans = max(ans, count[root])

        return ans
38709