主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的整數陣列 nums，而你被允許在其索引值上探訪。你可以在索引值 i 和索引值 j（i != j）之間自由探訪若且唯若 gcd(nums[i], nums[j]) > 1，其中 gcd 代表著最大公因數（Greatest Common Divisor）。
你的任務是判斷 nums 中每一對索引值 i 和 j，其中 i < j，是否都存在著一個探訪序列使得我們可以從 i 走到 j。
如果可以在所有索引值對之間探訪則回傳真（True）；反之回傳假（False）。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [2,3,6]
輸出： true
解釋： 在此例中，有 3 對可能的索引值對：(0, 1) 、 (0, 2) 和 (1, 2)。
從索引值 0 到 1，我們可以藉由序列 0 -> 2 -> 1 來探訪，其中我們從索引值 0 移動到索引值 2 因為 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1，而接著從索引值 2 移動到索引值 1 因為 gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1。
從索引值 0 到 2，我們可以直接走過去因為 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1。相似地，從索引值 1 到索引值 2，我們也可以直接走過去因為 gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1。
範例 2：
輸入： nums = [3,9,5]
輸出： false
解釋： 此例中索引值 0 和 2 之間不存在著探訪序列，所以我們回傳假。
範例 3：
輸入： nums = [4,3,12,8]
輸出： true
解釋： 在此例中，有 6 對可能的索引值對：(0, 1) 、 (0, 2) 、 (0, 3) 、 (1, 2) 、 (1, 3) 和 (2, 3)。每一對都存在著一個合法的探訪序列，因此我們回傳真。
解題思維：
首先，我們看 nums 中裡面有幾個數字 1 存在（假設有 C 個）。
如果 C > 1，則可以看到這 C 個 1 之間不存在探訪序列，因此不論其他數字如何便可以直接回傳假；如果 C == 1，則判斷 nums 的長度是否也為 1。如果是，則回傳真；反之，則其他數字與那個 1 不存在探訪序列，因此回傳假。
經過上面的篩選後，此時的 nums 不會有任何的 1 存在。並假設此時 nums 中最大的數字為 M。
接著先根據這題提及的方式（即埃式篩法）建立出質數表。接著，我們對於每一個質數 p 窮舉出其所有可能的倍數直到超過 M 為止，即 p 、 2p 、 3p 、……。
而這些倍數可能會出現在 nums 中（可以事先建立雜湊表或是直接使用陣列來儲存各種數字是否有出現於 nums 中）。
令 p 的倍數中有出現於 nums 中的那些數字為 q0 、 q1 、 q2 、 …… 、 qk。
可以看到根據題目 q0 、 q1 等這些數字的「索引值」之間可以互相來往。而如果有另一個質數 p'，其倍數有與 q0 、 q1 等有所重疊，則兩個質數之間的倍數可以根據重疊的部份來互相來往。而多個質數也是同理。
因此可以看到這個重疊關係可以視為是一種「集合」，因此可以使用併查集（Union-Find Set，參見這題的介紹）來維護這些數字是不是在同一個「集合」。
而最後只要看 2 ～ M 這 M - 1 種數字有出現在 nums 裡面的是否都是在同一個集合便可以知道是不是所有索引值對之間都有探訪序列。
總體時間複雜度為以下總和：
O(n)，用來找到 nums 中 1 的數量 、 最大值 M 以及建立可以用來查詢數字是否存在的資料結構，範例程式碼中是直接使用布林陣列來查詢。其中 n 為 nums 之長度、
O(M × log(log(M)))，用埃式篩法來建立小於等於 M 的質數表。不過範例程式碼中是用稍微改良後的，時間複雜度實際上是 O(M)，但不影響總體時間複雜度分析結果、
O(M × log(log(M)))，對每一個滿足 p < M 的質數 p 窮舉其倍數。可以看到總個數為 M × (1 / 2 + 1 / 3 + 1 / 5 + 1 / 7 + ……)，而質數倒數和之級數成長速度為 log(log(M))（參見維基頁面之說明）、
O(M × α(M))，一般併查集的總體時間複雜度。
因此總體為 O(n) + O(M × log(log(M)))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
