For those who are stuck with TLE even though UnionFind is used
It\'s easy to come up with unionfind (UF) as the solution. And there is good algorithm to generate all the prime numbers no bigger than n (denote as P(n)).\n\nH
It\'s easy to come up with unionfind (UF) as the solution. And there is good algorithm to generate all the prime numbers no bigger than n (denote as P(n)).\n\nHowever, a O(nP(n)) solution is still too slow. The tricky part is here: don\'t waste time on trying prime number p on every A[i]. Consider how you calculate the prime numbers under n: choose a number 2, mark all its multiples as false (non-prime). Then you go to 3, and 5, ... (4 is skipped because it has been marked in the round of 2). Together the time complexity is A[i]max(1/2+1/3+1/5+...). This is smaller than the famous Harmonic series (https://en.wikipedia.org/wiki/Harmonic_series_(mathematics) which grows very slowly.\n\nSimilar idea can be used after we have our candidate prime numbers. We choose a prime number (say, 2) and find are the multiple of 2\'s in the given array A. If so, union them together (Actually union all the index with the first i where A[i]%2==0). Then do the case of 3, 5, 7, .... By HashMap (with A[i] as key and i as value). every prime number (denote as p) needs A[i]max/p steps. And the total time complexity for the second half is O(A[i]max*(1/2+1/3+1/5+...). This should pass the test cases.\n\n```\nint[] id,size;\n    public int largestComponentSize(int[] A) {\n        Arrays.sort(A);\n        int n = A.length;\n        id = new int[n];\n        size = new int[n];\n        for(int i=0;i<n;i++){\n            id[i] = i;\n            size[i] = 1;\n        }\n        int max = Math.max(10,A[A.length-1]);\n\t\t\n\t\t// find out all the prime numbers that are no bigger than A[i]_max\n        boolean[] pri = new boolean[max+1];\n        Arrays.fill(pri,true);\n        ArrayList<Integer> prime = new ArrayList<>();\n        for(int i=2;i<=max;i++){\n            if(!pri[i]) continue;\n            prime.add(i);\n            for(int j=i;j<=max;j+=i) pri[j]=false;\n        }\n\t\t\n        HashMap<Integer,Integer> node = new HashMap<>();\n        for(int i=0;i<A.length;i++) node.put(A[i],i);\n        for(int w:prime){\n            int last = -1;\n\t\t\t// last >= 0 means that there is at least one A[i] that is a multiple of w. Union all other index with it\n            for(int i=w;i<=A[n-1];i+=w){\n                if(!node.containsKey(i)) continue;\n                if(last<0) last = node.get(i);\n                else{\n                    union(last,node.get(i));\n                }\n            }\n        }\n        int ans = 1;\n        for(int i=0;i<n;i++){\n            ans = Math.max(ans,size[find(i)]);\n        }\n        return ans;\n    }\n    public int find(int p){\n        while(p!=id[p]){\n            id[p] = id[id[p]];\n            p = id[p];\n        }\n        return id[p];\n    }\n    public void union(int p, int q){\n        int i = find(p);\n        int j = find(q);\n        if(i==j) return;\n        if(size[i]<size[j]){\n            id[i]=j;\n            size[j]+=size[i];\n        }else{\n            id[j]=i;\n            size[i]+=size[j];\n        }\n    }\n\t```\nSorry for the weird English I might have used. Please feel free to ask any question.\n
[]