Solution
C++ []\nclass Solution {\npublic:\n    int arr[(int)(1e5+5)];\n    int visit[(int)(1e5+5)]={0};\n    int member[(int)(1e5+5)];\n    constexpr void build(vector<
```C++ []\nclass Solution {\npublic:\n    int arr[(int)(1e5+5)];\n    int visit[(int)(1e5+5)]={0};\n    int member[(int)(1e5+5)];\n    constexpr void build(vector<int>& primes, pair<int,int>* sp, int N){\n        if(primes.empty()){\n            visit[0] = visit[1] = 1;\n            sp[1].first = sp[1].second = 1;\n            for(int i=2;i<=1e5;i++){\n                if(!visit[i]){\n                    primes.push_back(i);\n                    sp[i].first=i;\n                    sp[i].second = i;\n                }for (int j=0; i*primes[j]<=1e5; j++){\n                     visit[i*primes[j]] = 1;\n                     sp[i*primes[j]].first = primes[j];\n                     sp[i*primes[j]].second = sp[i].first == primes[j] ? sp[i].second : i;\n                     if(i%primes[j]==0)break;\n                 }\n            }\n        }\n        for(int i=0;i<=N;i++){\n            arr[i] = i;\n        }\n    }\n    int find(int x){\n        while(arr[x]!=x)\n            x=arr[x];\n        return x;\n    }\n    void uni(int x, int y){\n        x = find(x), y = find(y);\n        if(x==y)return;\n        member[y]+=member[x];\n        member[x]=0;\n        arr[x] = y;\n    }\n    int largestComponentSize(vector<int>& nums) {\n        static vector<int> primes;\n        static pair<int,int> sp[(int)(1e5+5)];\n        build(primes, sp, *max_element(nums.begin(),nums.end()));\n        int ans=1;\n        for(auto& it:nums){\n            int pre=sp[it].first;\n            it = sp[it].second;\n            while(it!=sp[it].first){\n                uni(sp[it].first, pre);\n                pre = sp[it].first;\n                it = sp[it].second;\n            }\n            uni(sp[it].first, pre);\n            member[find(pre)]++;\n            ans = max(member[find(pre)], ans);\n        }\n        return ans;\n    }\n};\n```\n\n```Python3 []\nMAXN = 10**5 + 5\nspf = list(range(MAXN))\n\ndef sieve():\n\tspf[1] = 1\n\n\tfor i in range(4, MAXN, 2):\n\t\tspf[i] = 2\n\n\tfor i in range(3, ceil(sqrt(MAXN))):\n\t\tif (spf[i] == i):\n\t\t\tfor j in range(i * i, MAXN, i):\n\t\t\t\tif (spf[j] == j):\n\t\t\t\t\tspf[j] = i\n\ndef factors(x: int):\n\tfactors_set = set()\n\n\twhile x != 1:\n\t\tfactors_set.add(spf[x])\n\t\tx //= spf[x]\n\n\treturn factors_set\n\nsieve()\n\nclass Solution:\n    def largestComponentSize(self, nums: List[int]) -> int:\n        df = {}\n        uf = UnionFind(len(nums))\n        for pos, num in enumerate(nums):\n            for factor in factors(num):\n                if factor in df:\n                    uf.union(pos, df[factor])\n                else:\n                    df[factor] = pos\n                    \n        return uf.mx\n            \nclass UnionFind:\n    def __init__(self, n: int):\n        self.root_lookup = list(range(n))\n        self.rank_lookup = [1] * n\n        self.mx = 1\n\n    def find(self, num: int):\n        root = self.root_lookup[num]\n        while root != self.root_lookup[root]:\n              root = self.root_lookup[root]\n        self.root_lookup[num] = root\n        return root\n    \n    def union(self, x, y):\n        xr, yr = self.find(x), self.find(y)\n        if xr == yr:\n            return False\n        if self.rank_lookup[xr] < self.rank_lookup[yr]:\n            xr, yr = yr, xr\n        self.root_lookup[yr] = xr\n        self.rank_lookup[xr] += self.rank_lookup[yr]\n        self.mx = max(self.mx,self.rank_lookup[xr])\n        return True\n```\n\n```Java []\nclass Solution {\n    public int gcd(int a, int b) {\n        if(a < b) {\n            int h = a;\n            a = b;\n            b = h;\n        }\n        while(b > 0) {\n            int h = b;\n            b = a % b;\n            a = h;\n        }\n        return a;\n    }\n    public int largestComponentSize(int[] nums) {\n        int n = nums.length;\n        int max = 1;\n        for(int num : nums) {\n            max = Math.max(max, num);\n        }\n        int[] m = new int[max + 1];\n        Arrays.fill(m, -1);\n        boolean[] check = new boolean[max + 1];\n        for(int i = 0; i < n; i++) {\n            m[nums[i]] = i;\n        }\n        UnionFind uf = new UnionFind(n);\n        for(int p = 2; p <= max; p++) {\n            if(check[p])\n                continue;\n\n            int first = -1;\n            for(int div = p; div <= max; div += p) {\n                if(m[div] >= 0) {\n                    if(first == -1) {\n                        first = m[div];\n                    } else {\n                        uf.join(first, m[div]);\n                    }\n                }\n                check[div] = true;\n            }\n        }\n        return uf.getMaxComponent();\n    }\n}\npublic class UnionFind {\n    private int[] parent;\n    private int[] size;\n    private int maxSize;\n\n    public UnionFind(int n) {\n        parent = new int[n];\n        size = new int[n];\n        maxSize = 1;\n\n        for(int i = 0; i < n; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n    }\n    public int find(int x) {\n        return x != parent[x] ? parent[x] = find(parent[x]) : x;\n    }\n    public void join(int x, int y) {\n        x = find(x);\n        y = find(y);\n\n        if(x != y) {\n            if(size[x] < size[y]) {\n                int h = x;\n                x = y;\n                y = h;\n            }\n            size[x] += size[y];\n            maxSize = Math.max(maxSize, size[x]);\n            parent[y] = x;\n        }\n    }\n    public int getMaxComponent() {\n        return maxSize;\n    }\n}\n```\n
['C++', 'Java', 'Python3']