Largest Component...  - javascript 356ms (beats 90%)
Ideas to the solution\n\n It doesn\'t need to have the entire graph, and we only need to have connected components with minimal connections.\n Using union-find 
### Ideas to the solution\n\n* It doesn\'t need to have the entire graph, and we only need to have connected components with minimal connections.\n* Using [union-find algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure), we can efficiently group two numbers divided by a divisor. However, running this algorithm will take O(N^2), and it causes TLE. \n* A key idea is that two numbers divided by a prime number belong to the same component together. Furthermore, K numbers are divided by a prime number will be in the same component. Running the union operation for (X1, X2), (X1, X3), ..., (X1, XK) will group the number together. Here, X1 ... XK is a set of numbers that are divided by a prime number.\n* So, using Eratosthenes\' sieve, we can collect prime numbers less than or equal to the maximum number (M) of the input and run the union operations.\n* My initial solution runs Eratosthenes\' sieve from 2 to M. It was accepted, but it took 4600 ms. After I got AC, I tried to find where I could optimize. \n* After review my code, I realized that it only needs to run the sieve up to sqrt(M) with prime factorizations for every time it performs a union operation for a prime number. Later the sieve, it needs to find numbers that still need to be factorized, and those numbers are prime numbers that are not counted by the sieve. Running additional union operations the same yet-to-factorized numbers (prime numbers) and measuring the maximum component will complete the algorithm. \n\n```\nvar largestComponentSize = function(A) {\n  const n = A.length;\n  let parent = new Array(n).fill().map((_,i)=>i);\n  let cnt = new Array(n).fill(1);\n  let find  = (i) => parent[i] == i? i : find(parent[i]);\n  let union = (i, j) => {\n    let p = find(i);\n    let q = find(j);\n    \n    if(p === q) return;\n    \n    if(cnt[p]<cnt[q]) {\n      [p,q] = [q,p];\n    }\n    cnt[p] += cnt[q];\n    parent[q] = p;\n  }\n  \n  const m = Math.max(...A);\n  let p = new Array(m+1).fill(true);\n  const root = Math.floor(Math.sqrt(m));\n  for(let i=2;i<=root;i++) if(p[i]) {\n    let k = -1;\n    for(let j=0;j<n;++j) {\n      if(A[j]%i===0) {\n        while(A[j] % i === 0)\n          A[j] = Math.floor(A[j]/i);\n        if(k===-1) k = j;\n        else union(k, j);\n      }\n    } \n    for(let j=i*i;j<=m;j+=i) p[j] = false;\n  }\n  \n  A = A.map((x,i)=>[x,i]).filter(x=>x[0]>1).sort((a,b)=>a[0]-b[0]);\n  for(let i=1;i<A.length;++i) {\n    if(A[i-1][0]===A[i][0]) {\n      union(A[i-1][1], A[i][1]);\n    }\n  }\n  \n  return Math.max(...cnt);\n};\n```
['Union Find', 'JavaScript']