Union by size + Prime factorization
Intuition  \nLargest component by size => Union by size\nShares common factor => we need to check all prime factors\n Describe your first thoughts on how to sol
# Intuition  \nLargest component by size => Union by size\nShares common factor => we need to check all prime factors\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nMake a hash table of integer , set.\nIn the hash table the key will be the array element (unique)\nand value will be a set of all prime factors of it.\nThen union each array elements with it\'s prime factors.\n\nused sieve of eratosthenes to generate all prime factors in logn.\nAt first for each array elements size[element] = 1 and\nsize of all other numbers will be 0.  So after union size of prime factors will not be counted.\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n * max number of prime factors among all nums[i]) + O(nlog(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:   O( max( nums[ i ] ) )\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    int parent [];\n    int size [];\n    public int largestComponentSize(int[] nums) {\n     int max = nums[0] ;\n     HashMap<Integer,HashSet<Integer>> primeFactors = new HashMap<>();\n     for(int val : nums)   max = Math.max(max,val);\n     int seive [] = new int[max + 1];\n     parent = new int[max + 1];\n     size  = new int[max + 1];\n\n     for(int i = 0; i < seive.length ; i++)   parent[i] = seive[i] = i;\n\n     for(int i = 2; i*i < seive.length ; i++){\n         if(seive[i] == i){\n             for(int j = i; j < seive.length ; j+=i){\n                 if(seive[j] == j) seive[j] = i;\n             }\n         }\n     }\n\n     for(int i = 0; i < nums.length ; i++){\n         int val = nums[i];\n         size[val] = 1;\n         HashSet<Integer> set = new HashSet<>();\n        addFactors(val,seive,set);\n         primeFactors.put(val,set);\n     }\n\n\n\n\n         for(int val : nums){\n             for(int fac : primeFactors.get(val)){\n             if(val % fac == 0){\n                 if(findparent(fac) != findparent(val)) {\n                  union(fac , val);\n                 }\n             }\n         }\n         }\n     \n\n    \n            int ans = 1;\n            for(int val : size) {\n                ans = Math.max(ans,val);\n            }\n            return ans;\n     \n\n    }\n\n    public int findparent(int node){\n         if(parent[node] == node) return node;\n         return parent[node] = findparent(parent[node]);\n    }\n\n    public void union(int u , int v){\n      u = findparent(u);\n      v = findparent(v);\n      if(size[u] > size[v]){\n          parent[v] = u;\n          size[u]+=size[v];\n      }else {\n        parent[u] = v;\n          size[v]+=size[u];\n      }\n    }\n\n    public void addFactors(int val, int seive [] , HashSet<Integer> set){\n          while(val > 1){\n              set.add(seive[val]);\n              val = val/seive[val];\n          }\n    }\n}\n```
['Array', 'Hash Table', 'Math', 'Union Find', 'Java']