題解

從題意觀察，可發現將任意數做質因數分解後
所有擁有這些質因數其中之一的，全部都能連成一塊

原題目可轉成將原圖所有數字的質因數建成一張圖
任兩質數同時作為原圖任一數字的質因數時
則這兩個質數之間有一條邊

最後留下多少組質數的連通圖，即為原題目所求
無向圖的連通可以用 union 來做，問題剩下質因數分解

做一次質數篩法，記錄每個數字被誰篩去
則每個數字能以 O(1) 時間得出任意一個質因數
除以任意一個質因數後，變成同性質小問題
最多有 log n 個質因數，故任意數質因數分解複雜度為 O(log n)

Time: 0.140, Rank: 6/86

來自小希的建議