Elegant Solution using Kotlin with Sieve of Eratosthenes  + BFS O(1.000.000)
The idea is to construct a Bipartite Graph with left vertices contain prime numbers, right vertices contain A[i]\n\n2    A[0]\n3    A[1]\n5    A[2]\n7    A[3]\n
The idea is to construct a Bipartite Graph with left vertices contain prime numbers, right vertices contain A[i]\n```\n2    A[0]\n3    A[1]\n5    A[2]\n7    A[3]\n...\n```\nand edges connect `left[l]` with `right[r]` satisfying `right[r] mod left[l] = 0`\nThe number of edges will < the complexity of Sieve of Eratosthenes, which is ~ `1000000`\nSo the problem become simple: find the largest connected component using `BFS` or `DFS`\nFor the sake of this problem, it\'s possible that A[i] = A[j], so instead of A in the right vertices, we instead use count map to count the number of occurance of each unique A member.\nComplexity: O (100000 * 10) for both `Sieve of Eratosthenes` and `BFS`\n```\nclass Solution {\n    fun largestComponentSize(A: IntArray): Int {\n        val count = A.toList().groupingBy { it }.eachCount().toMutableMap()\n        val left = mutableMapOf<Int, MutableSet<Int>>()\n        val right = mutableMapOf<Int, MutableSet<Int>>()\n        val prime = BooleanArray(100001, { _ -> true })\n        for (p in 2 until 100001) {\n            if (prime[p]) {\n                for (d in IntProgression.fromClosedRange(p, 100000, p)) {\n                    if (d > p) prime[d] = false\n                    if (count.containsKey(d)) {\n                        left.computeIfAbsent(p, { _ -> hashSetOf() }).add(d)\n                        right.computeIfAbsent(d, { _ -> hashSetOf() }).add(p)\n                    }\n                }\n            }\n        }\n\n        var max = 0\n        while (left.isNotEmpty()) {\n            val queue = mutableSetOf<Int>()\n            var sum = 0\n            queue.add(left.keys.first())\n            while (queue.isNotEmpty()) {\n                val l = queue.first().also { queue.remove(it) }\n                val rs = left.remove(l) ?: emptyList<Int>()\n                for (r in rs) {\n                    sum += count.remove(r) ?: 0\n                    queue.addAll((right.remove(r) ?: mutableSetOf()).toList())\n                }\n            }\n            max = kotlin.math.max(max, sum)\n        }\n\n        return max\n    }\n}\n```
[]