class DisjointSet {
    vector<int> rank, parent, size;
    
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]); // Path compression
    }

    void unionByRank(int u, int v) {
        int pu = findUPar(u);
        int pv = findUPar(v);
        if (pu == pv) return;

        if (rank[pu] < rank[pv]) {
            parent[pu] = pv;
        } else if (rank[pv] < rank[pu]) {
            parent[pv] = pu;
        } else {
            parent[pv] = pu;
            rank[pu]++;
        }
    }

    void unionBySize(int u, int v) {
        int pu = findUPar(u);
        int pv = findUPar(v);
        if (pu == pv) return;

        if (size[pu] < size[pv]) {
            parent[pu] = pv;
            size[pv] += size[pu];
        } else {
            parent[pv] = pu;
            size[pu] += size[pv];
        }
    }
};

class Solution {
public:
    vector<int> sp(int n) {
        vector<int> spf(n + 1);
        for (int i = 0; i <= n; ++i) spf[i] = i;
        for (int i = 2; i * i <= n; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        return spf;
    }

    vector<int> fac(int x, vector<int>& spf) {
        vector<int> f;
        while (x > 1) {
            int p = spf[x];
            f.push_back(p);
            while (x % p == 0) x /= p;
        }
        return f;
    }

    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        int maxNum = *max_element(nums.begin(), nums.end());

        vector<int> spf = sp(maxNum);
        DisjointSet ds(maxNum + 1);

        for (int num : nums) {
            vector<int> primes = fac(num, spf);
            for (int prime : primes) {
                ds.unionBySize(num, prime); // Union by size
            }
        }

        unordered_map<int, int> cnt;
        int maxSize = 0;
        for (int num : nums) {
            int root = ds.findUPar(num);
            cnt[root]++;
            maxSize = max(maxSize, cnt[root]);
        }

        return maxSize;
    }
};