C++ 84 ms O(n * 65)
For each number, we find all prime factors, group these factors using union-find, and count how many numbers are in each group.\n\nSince the maximum value is 10
For each number, we find all prime factors, group these factors using union-find, and count how many numbers are in each group.\n\nSince the maximum value is 100,000,  we only need primes till 313 (317 * 317 = 100,489). The intuition here is that we do not need to care about large primes as they won\'t connect to any other number. So, our union-find structure only needs to have 65 elements.\n\nNow, numbers like 2, 3, 401, 802, 1203 are tricky (all in the same group). 802 (2 * 401) adds a previous prime to group "2", and 1203 (3 * 401) joins groups "2" and "3". So, we do need to track large primes, *but only when they appear in the input sequence*.\n\nIf after trying all 65 factors the remainder is greater than 1, it\'s a large prime. We use a hash map to track our large primes and the factor it\'s \'connected\' to.\n```\nvector<int> factors = {\n    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,\n    103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,\n    199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313\n};\nvoid uf_union(vector<int>& uf, int p1, int p2) {\n  auto pp1 = uf_find(uf, p1), pp2 = uf_find(uf, p2);\n  if (pp1 != pp2) uf[pp1] += uf[pp2], uf[pp2] = pp1;\n}\nint uf_find(vector<int>& uf, int p) {\n  if (uf[p] <= 0) return p;\n  return uf[p] = uf_find(uf, uf[p]);\n}\nint largestComponentSize(vector<int>& A) {\n  unordered_map<int, int> primes;\n  vector<int> uf(factors.size(), 0);\n  for (auto a : A) {\n    auto last_f = -1;\n    for (auto i = 0; i < factors.size() && factors[i] <= a; ++i) {\n      if (a % factors[i] == 0) {\n        while (a % factors[i] == 0) a /= factors[i];\n        if (last_f >= 0) uf_union(uf, i, last_f);\n        last_f = i;\n      }\n    }\n    if (a > 1) {\n      auto it = primes.find(a);\n      if (it != primes.end()) {\n        if (last_f != -1 && it->second != -1) uf_union(uf, last_f, it->second);\n        else if (last_f != -1 || it->second != -1) uf[uf_find(uf, max(last_f, it->second))] -= 1;\n      }\n      if (it == primes.end() || last_f >= 0) primes[a] = last_f;\n    }\n    if (last_f >= 0) uf[uf_find(uf, last_f)] -= 1;\n  }\n  return -*min_element(begin(uf), end(uf));\n}\n```
[]