952. Largest Component Size by Common Factor

Largest Component Size by Common Factor

題目描述： 給定一個正整數陣列 nums，如果 nums[i] 和 nums[j] 有大於 1 的公因數，就在它們之間連一條邊。求最大連通分量的大小。

解題思路：

1. Union-Find + 質因數分解：對每個數字做質因數分解。如果兩個數字共享一個質因數，它們就在同一個連通分量中。
2. 對每個數字 nums[i]，找出其所有質因數。將 nums[i] 與每個質因數合併（Union）。
3. 共享質因數的數字會通過該質因數間接地被合併到同一個集合。
4. 最後統計每個集合中包含多少個原始數字（非質因數），取最大值。
5. 關鍵優化：不直接對數字配對（O(n^2)），而是通過質因數作為中間節點進行合併。

時間複雜度：O(n * sqrt(M) * α(M)) — n 為陣列長度，M 為最大值。每個數字的質因數分解 O(sqrt(M))，Union-Find 操作近乎 O(1)

空間複雜度：O(M) — Union-Find 陣列大小為最大值 M

1. Sieve + Union-Find：用類似埃拉托斯特尼篩法的方式，對每個質數 p，將所有陣列中 p 的倍數合併。避免了逐個質因數分解的開銷。

2. 建圖 + DFS/BFS：顯式地對共享因數的數字建邊，然後用 DFS/BFS 找連通分量。但建邊可能需要 O(n^2) 時間，且邊數可能爆炸。

1. 如果不是「有公因數」而是「互質」時才連邊，最大連通分量的大小是多少？
2. 如何高效地動態增加或刪除數字，並維護最大連通分量？
3. 如果改為有向圖（a 的所有因數都有邊指向 a），最長路徑是多少？