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 = "class Solution:\n    def largestComponentSize(self, A: List[int]) -> int:\n        n=len(A)\n        if n<2:\n            return n\n        A=set(A)\n        if 1 in A:\n            A.remove(1)\n        if len(A)==0:\n            return 1\n        #A=list(A)\n        #A.sort()\n        \n        def list_primes(m):\n            p=[True]*(m+1)\n            for i in range(2,m+1):\n                if p[i]:\n                    for j in range(2*i,m+1,i):\n                        p[j]=False\n            return [i for i in range(2,m+1) if p[i]]\n        \n        def find_prime_factors(x,prime_list,prime_set):\n            if x in prime_set:\n                return [x]\n            prime_factors=[]\n            for prime_num in prime_list:\n                if prime_num*prime_num>x:\n                    break\n                if x%prime_num==0:\n                    prime_factors.append(prime_num)\n                    while x%prime_num==0:\n                        x//=prime_num\n            if x!=1:\n                prime_factors.append(x)\n            return prime_factors\n        \n        def prime_decompose(x):\n            f=2\n            prime_factors=[]\n            while x>=f*f:\n                if x%f==0:\n                    prime_factors.append(f)\n                    x//=f\n                else:\n                    f+=1\n            prime_factors.append(x)\n            return prime_factors\n        #print(prime_decompose(60))\n        #print(prime_decompose(5120))\n        #return 0\n        \n        prime_list=list_primes(max(A))\n        prime_set=set(prime_list)\n        #print(prime_list)\n        d={x:find_prime_factors(x,prime_list,prime_set) for x in A}\n        #d={x:list(set(prime_decompose(x))) for x in A}\n        #print([len(d[x]) for x in A])\n        all_factors=set()\n        for x in A:\n            for f in d[x]:\n                all_factors.add(f)\n        #print(all_factors)\n        find_dict={f:f for f in all_factors}\n        sink_size={f:1 for f in all_factors}\n        def find(f):\n            if find_dict[f]!=f:\n                find_dict[f]=find(find_dict[f])\n            return find_dict[f]\n        \n        def union(fi,fj):\n            sink_i=find(fi)\n            sink_j=find(fj)\n            if sink_i==sink_j:\n                return\n            if sink_size[sink_i]>sink_size[sink_j]:\n                find_dict[sink_j]=sink_i\n                sink_size[sink_i]+=sink_size[sink_j]\n            else:\n                find_dict[sink_i]=sink_j\n                sink_size[sink_j]+=sink_size[sink_i]\n        \n        def union_hyperedge(hyperedge):\n            for i in range(1,len(hyperedge)):\n                union(hyperedge[i],hyperedge[0])\n            \n        def union_no_load_balance(hyperedge):\n            sink=find(hyperedge[0])\n            for f in hyperedge:\n                find_dict[find(f)]=sink\n                find(f)\n            \n        for x in A:\n            union_hyperedge(d[x])\n        #print('Union done.')\n        sinks=set()\n        for f in all_factors:\n            sinks.add(find(f))\n        \n        count={sink:0 for sink in sinks}\n        \n        for x in A:\n            count[find(d[x][0])]+=1\n        \n        return max(count.values())\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: 11392