Java Simple O(N*sqrt(W)) Union Find Solution
We maintain a union set where several elements are connected if and only if they have any common factor greater than 1.\nWe only have to connect each element in
We maintain a union set where several elements are connected if and only if they have any common factor greater than 1.\nWe only have to connect each element in *A* with all its factors greater than 1, according to the nature of union set. We can do this by simply checking all the integers ranging from 2 to sqrt(A[i]).\n```\nclass Solution {\n    \n    int[] p;\n    \n    int get(int x){\n        return p[x]==x ? x : (p[x]=get(p[x])) ;\n    }\n    \n    void add(int x, int y){\n        p[get(x)]=p[get(y)];\n    }\n    \n    public int largestComponentSize(int[] A) {\n        int mx=0;\n        for(int i:A) mx=Math.max(i, mx);\n        p=new int[mx+1];\n        for(int i=1;i<=mx;++i) p[i]=i;\n        for(int i:A)\n            for(int j=(int)Math.sqrt(i);j>=2;--j)\n                if(i%j==0){\n                    add(i, j);\n                    add(i, i/j);\n                }\n        Map<Integer, Integer> map=new HashMap<Integer, Integer>();\n        int res=0;\n        for(int i:A){\n            int j=get(i);\n            if(!map.containsKey(j)) map.put(j, 1);\n            else map.put(j, map.get(j)+1);\n            res=Math.max(res, map.get(j));\n        }\n        return res;\n    }\n}\n```
[]