C# solution: Prime factorization + Union Find
\npublic class Solution \n{\n    private  Dictionary<int, int> dict = new Dictionary<int, int>();\n    private  Dictionary<int, int> count = new Dictionary<int,
```\npublic class Solution \n{\n    private  Dictionary<int, int> dict = new Dictionary<int, int>();\n    private  Dictionary<int, int> count = new Dictionary<int, int>();\n    private  Dictionary<int, List<int>> group = new Dictionary<int, List<int>>();\n    public int LargestComponentSize(int[] a) \n    {\n        var primes = new HashSet<int>();\n        var isPrime = Enumerable.Repeat(true, 100001).ToArray();\n        for (int i = 2; i <= 100000; i++) \n        {\n            if (isPrime[i]) \n            {\n                primes.Add(i);\n                for (int j = 2; j * i <= 100000; j++) isPrime[j * i] = false;\n            }\n        }\n        \n        foreach(var num in a)\n        {\n            int n = num;\n            foreach(var prime in primes)\n            {\n                if(prime > n) break;\n                else if(primes.Contains(n))\n                {\n                    if(!group.ContainsKey(n)) group[n] = new List<int>();\n                    group[n].Add(num);\n                    break;\n                }\n                else if(n % prime == 0)\n                {\n                    if(!group.ContainsKey(prime)) group[prime] = new List<int>();\n                    group[prime].Add(num);\n                    n = n / prime;\n                }\n            }\n        }\n        \n       foreach(var kvp in group)\n       {\n           var l = kvp.Value;\n           for(int i = 0; i < l.Count -1 ; i++)\n           {\n               int j = i + 1;\n               int p1 = GetParent(l[i]), p2 = GetParent(l[j]);\n               if(p1 != p2)\n               {\n                    dict[p1] = p2;\n                    count[p2] = count[p1] + count[p2];\n                }\n            }\n        }\n        \n        return count.Values.Max();\n    }\n    \n    private int GetParent( int n)\n    {\n       if(!dict.ContainsKey(n))\n       {\n           dict[n] = n;\n           count[n] = 1;\n       }\n        if(dict[n] != n) dict[n] = GetParent(dict[n]);\n        return dict[n];\n    }\n}\n```
[]