Prime Factorization and Union Find
Calculate all prime numbers less than 100000.\n2. For each number in A, we say A[i]\n\ta. Do Prime Factorization(Brute force using the primes set in step 1), we
1. Calculate all prime numbers less than `100000`.\n2. For each number in `A`, we say `A[i]`\n\ta. Do Prime Factorization(Brute force using the primes set in step 1), we say the prime factor is `p`.\n\tb. If `p` has presented in the `primeToIndex`, union `i` and `primeToIndex[p]`.\n\tc. Update `primeToIndex[p]` to `i`.\n3. Return the maximum count.\n\nTime complexity: `O(NP)`, where `P` is the count of prime numbers < `100000`. I think this is an upperbound time complexity.\n```\nclass Solution {\n    int max = 0;\n    public int largestComponentSize(int[] A) {\n        boolean[] isPrime = new boolean[100001];\n        Arrays.fill(isPrime, true);\n        Set<Integer> primes = new HashSet<>();\n        // all primes less than 100000\n        for (int i = 2; i <= 100000; i++) {\n            if (isPrime[i]) {\n                primes.add(i);\n                for (int j = 2; j * i <= 100000; j++) {\n                    isPrime[j * i] = false;\n                }\n            }\n        }\n        int n = A.length;\n        int[] counts = new int[n];\n        int[] parents = new int[n];\n        int[] primeToIndex = new int[100001];\n        Arrays.fill(primeToIndex, -1);\n        for (int i = 0; i < n; i++) {\n            parents[i] = i;\n            counts[i] = 1;\n        }\n        for (int i = 0; i < n; i++) {\n            int a = A[i];\n            for (int p : primes) {\n                if (primes.contains(a)) { // Optimization\n                    p = a;\n                }\n                if (a % p == 0) {\n                    if (primeToIndex[p] > -1) {\n                        union(parents, counts, primeToIndex[p], i);\n                    }\n                    primeToIndex[p] = i;\n                    while (a % p == 0) {\n                        a /= p;\n                    }\n                }\n                if (a == 1) {\n                    break;\n                }\n            }\n        }\n        return max;\n    }\n    private int find(int[] parents, int a) {\n        if (parents[a] != a) {\n            parents[a] = find(parents, parents[a]);\n        }\n        return parents[a];\n    }\n    private void union(int[] parents, int[] counts, int a, int b) {\n        int root1 = find(parents, a), root2 = find(parents, b);\n        if (root1 == root2) {\n            return;\n        }\n        int count = counts[root2] + counts[root1];\n        max = Math.max(count, max);\n        parents[root1] = root2;\n        counts[root2] = count;\n    }\n}\n```
[]