题目传送门
首先明确，1不是质数，故质因子中不包含1。

利用线性筛法求解质因子。

bool isPrime[100005] = {0};
int prime[100005] = {0};
int lpf[100005] = {0};
int tot = 0;
int init = [](){memset(isPrime,true,sizeof(isPrime));for(int i = 0;i<100005;i++){lpf[i] = i;}for(int i = 2;i<=100000;i++){if(isPrime[i]){prime[tot++] = i;}for(int j = 0;j<tot && i*prime[j] <= 100000;j++){isPrime[i*prime[j]] = false;lpf[i*prime[j]] = prime[j];if(i%prime[j] == 0)break;}}return 0;
}();

小技巧：

在后续构建并查集时，可以通过索引来构建并查集，nums数组中点的索引作为一个点集，所有(质因子+n)作为一个点集，这样可以避免对1的特判，因为当数组中全为1时，那么对于并查集来说是连通的，但是实际上并不符合题意。
完整代码：

bool isPrime[100005] = {0};
int prime[100005] = {0};
int lpf[100005] = {0};
int tot = 0;
int init = [](){memset(isPrime,true,sizeof(isPrime));for(int i = 0;i<100005;i++){lpf[i] = i;}for(int i = 2;i<=100000;i++){if(isPrime[i]){prime[tot++] = i;}for(int j = 0;j<tot && i*prime[j] <= 100000;j++){isPrime[i*prime[j]] = false;lpf[i*prime[j]] = prime[j];if(i%prime[j] == 0)break;}}return 0;
}();
class Solution {int fa[200005] = {0};int find(int a){if(fa[a] != a){fa[a] = find(fa[a]);}return fa[a];}void merge(int a,int b){int f1 = find(a),f2 = find(b);fa[f1] = f2;}public:bool canTraverseAllPairs(vector<int>& nums) {int n = nums.size();for(int i = 0;i<200005;i++){fa[i] = i;}for(int i = 0;i<n;i++){int val = nums[i];while(val != 1){merge(i,lpf[val]+n);val /= lpf[val];}}for(int i = 0;i<n;i++){//cout<<find(i)<<endl;if(find(i) != find(0)){return false;}}return true;}
};

时间复杂度分析

[1~n]范围内的质数个数为$\frac{n}{log(n)}$,预处理得到每个数字的最小质因子后，$log(n)$时间即可得到所有的质因子，那么时间复杂度为$O(nlog(n))$