Given a non-empty array of unique positive integers A, consider the following graph:

There are A.length nodes, labelled A[0] to A[A.length - 1];
There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.
 



Example 1:
Input: [4,6,15,35]
Output: 4



Example 2:
Input: [20,50,9,63]
Output: 2



Example 3:
Input: [2,3,6,7,4,12,21,39]
Output: 8


Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import numpy as np\nclass Solution:\n    def largestComponentSize(self, A: List[int]) -> int:\n        # second attempt, going factor-wise using disjoint set structure\n        # A = np.array(A)\n        # start with parent pointing to themselves\n        parents = np.arange(len(A))\n        \n        # count of each node starting at 1 (itself)\n        counts = np.ones_like(parents)\n        \n        def find(i):\n            if parents[i] == i:\n                return i\n            else:\n                return find(parents[i])\n        \n        def combine(i, j):\n            pi = find(i)\n            pj = find(j)\n            \n            # only do something if not already linked\n            if pi != pj:\n                # merge under the biggest root\n                if counts[pi] > counts[pj]:\n                    parents[pj] = pi\n                    counts[pi] += counts[pj]\n                else:\n                    parents[pi] = pj\n                    counts[pj] += counts[pi]\n        \n        max_prime = int(np.floor(np.sqrt(max(A))))+1\n        # max_prime = max(A)\n        \n#         def get_primes(value: int) -> List[int]:\n#             ret = []\n#             sieve = [True]*(value+1)\n#             for p in range(2, value+1):\n#                 if sieve[p]:\n#                     ret.append(p)\n#                     for k in range(p, value+1, p):\n#                         sieve[k] = False\n#             return ret\n        \n#         primes = get_primes(max_prime)\n        \n#         for prime in primes:\n#             match = -1\n#             for i in range(len(A)):\n#                 if A[i] % prime == 0:\n#                     while A[i] % prime == 0:\n#                         A[i] = A[i] // prime  # keep factoring out\n#                     if match != -1:\n#                         # do the merge\n#                         combine(match, i)\n#                     else:\n#                         match = i # first one found, merge from now on\n        \n        \n        sieve = [True]*(max_prime+1)\n        for prime in range(2, max_prime+1):\n            if sieve[prime]:\n                match = -1\n                for i in range(len(A)):\n                    if A[i] % prime == 0:\n                        while A[i] % prime == 0:\n                            A[i] = A[i] // prime  # keep factoring out\n                        if match != -1:\n                            # do the merge\n                            combine(match, i)\n                        else:\n                            match = i # first one found, merge from now on\n                for k in range(prime, max_prime+1, prime):\n                    sieve[k] = False\n        \n        # leftover values of A are now higher primes (or 1)\n        # if any match, they need to be merged\n        inds = np.argsort(A)\n        \n        # print(A)\n        # print(inds)\n        # print(A[inds])\n        for i in range(1,len(A)):\n            if (A[inds[i]] != 1) and (A[inds[i-1]] == A[inds[i]]):\n                combine(inds[i-1], inds[i])\n        \n        return np.max(counts)\n        \n        # first attempt\n        # TLE at 78/100\n#         # note: a value of 1 cannot be connected to anything\n#         # can clump things together based on factors\n        \n#         def get_factors(value: int) -> List[int]:\n#             if value == 1:\n#                 return set()\n#             # ret = [value]\n#             ret = set([value])\n            \n#             # if value % 2 == 0:\n#             #     ret.append(2)\n#             #     ret.append(value // 2)\n            \n#             for i in range(2, int(np.floor(np.sqrt(value)))+1):\n#                 if value % i == 0:\n#                     ret.add(i)\n#                     ret.add(value // i)\n#                     # ret.append(i)\n#                     # ret.append(value // i)\n            \n#             return ret\n#             # return set(ret)\n        \n        \n#         # def get_primes(value: int) -> List[int]:\n#         #     ret = []\n#         #     sieve = [True]*(value+1)\n#         #     for p in range(2, value+1):\n#         #         if sieve[p]:\n#         #             ret.append(p)\n#         #             for k in range(p, value+1, p):\n#         #                 sieve[k] = False\n#         #     return ret\n        \n#         # trying more efficient get_primes implementation\n#         # def get_primes(n: int) -> List[int]:\n#         #     # modified from\n#         #     # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188\n#         #     sieve = np.ones(n//3 + (n%6==2), dtype=np.bool)\n#         #     sieve[0] = False\n#         #     for i in range(int(n**0.5)//3+1):\n#         #         if sieve[i]:\n#         #             k=3*i+1|1\n#         #             sieve[      ((k*k)//3)      ::2*k] = False\n#         #             sieve[(k*k+4*k-2*k*(i&1))//3::2*k] = False\n#         #     return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]\n        \n#         def get_primes(n: int) -> List[int]:\n#             sieve = [True] * n\n#             for i in range(3,int(n**0.5)+1,2):\n#                 if sieve[i]:\n#                     sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)\n#             return [2] + [i for i in range(3,n,2) if sieve[i]]\n        \n#         primes = get_primes(int(np.floor(np.sqrt(max(A))))+1)\n#         # primes = get_primes(max(A))\n        \n#         def get_factors(value: int) -> List[int]:\n#             ret = set([value])\n#             for prime in primes:\n#                 if prime > value:\n#                     return ret\n#                 else:\n#                     if value % prime == 0:\n#                         ret.add(prime)\n#                         while value % prime == 0:\n#                             value /= prime\n                        \n#                         # ret.add(value//prime)\n#                         # value /= prime  # factor out prime for efficiency\n#                         # while value % prime == 0:\n#                         #     ret.add(value//prime)\n#                         #     value /= prime\n                        \n#                         # if value // prime in primes:\n#                         # ret.add(value//prime)\n#                         # value /= prime  # factor out prime for efficiency\n#                         # if value > 1:\n#                         #     ret.add(value)\n#                         # else:\n#                         #     break\n#                         # while value % prime == 0:\n#                         #     # if value // prime in primes:\n#                         #     # ret.add(value//prime)\n#                         #     value /= prime\n#                         #     if value > 1:\n#                         #         ret.add(value)\n#                         #     else:\n#                         #         break\n#             if value > 1:\n#                 ret.add(value)\n#             return ret\n        \n#         clusters = []\n#         sizes = []\n        \n#         for value in A:\n#             factors = get_factors(value)\n#             # check cluster matches, all that get matched get merged\n#             matches = []\n#             for j, cluster in enumerate(clusters):\n#                 if not cluster.isdisjoint(factors):\n#                     matches.append(j)\n#             # if not in any cluster, make a new cluster\n#             if len(matches) == 0:\n#                 clusters.append(factors)\n#                 sizes.append(1)\n#             elif len(matches) == 1:\n#                 clusters[matches[0]].update(factors)\n#                 sizes[matches[0]] += 1\n#             else:\n#                 base = matches[0]\n#                 # iterate backwards so they can be deleted safely\n#                 for match in matches[-1:0:-1]:\n#                     clusters[base].update(clusters[match])\n#                     sizes[base] += sizes[match]\n#                     del clusters[match]\n#                     del sizes[match]\n                \n#                 # add the new factors\n#                 clusters[base].update(factors)\n#                 sizes[base] += 1      \n\n#         return max(sizes)\n            \n        \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'largestComponentSize'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 14908