Simplest Solution (Union Find only) No Prime Calculation
Union Find template. The only additional stuff is one hashmap which is used to convert factor to the node index in A for union. \nHashMap: key is the factor, va
Union Find template. The only additional stuff is one hashmap which is used to convert factor to the node index in A for union. \nHashMap: key is the factor, val is the index in A\nTime complexity: O(N*sqrt(Max val of A[i]))\n```\nclass Solution {\n    class UF {\n        int[] parent;\n        int[] size;\n        int max;\n        public UF (int N){\n            parent = new int[N];\n            size = new int[N];\n            max = 1;\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            if (x == parent[x]){\n                return x;\n            }\n            return parent[x] = find(parent[x]);\n        }\n        public void union(int x, int y){\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX != rootY){\n                parent[rootX] = rootY;\n                size[rootY] += size[rootX];\n                max = Math.max(max, size[rootY]);\n            }\n        }\n    }\n    public int largestComponentSize(int[] A) {\n        int N = A.length;\n        Map<Integer, Integer> map = new HashMap<>();// key is the factor, val is the node index\n        UF uf = new UF(N);\n        for (int i = 0; i < N; i++){\n            int a = A[i];\n            for (int j = 2; j * j <= a; j++){\n                if (a % j == 0){\n                    if (!map.containsKey(j)){//this means that no index has claimed the factor yet\n                        map.put(j, i);\n                    }else{//this means that one index already claimed, so union that one with current\n                        uf.union(i, map.get(j));\n                    }\n                    if (!map.containsKey(a/j)){\n                        map.put(a/j, i);\n                    }else{\n                        uf.union(i, map.get(a/j));\n                    }\n                }\n            }\n            if (!map.containsKey(a)){//a could be factor too. Don\'t miss this\n                map.put(a, i);\n            }else{\n                uf.union(i, map.get(a));\n            }\n        }\n        return uf.max;\n    }\n}\n```
[]