Problem - Largest Component Size by Factor

Given an array of unique positive integers, connect two numbers if they share a common factor greater than 1. Return the size of the largest connected component.

Example: $[4, 6, 15, 35]$ returns $4$. - $4$ and $6$ share factor $2$

• $6$ and $15$ share factor $3$
• $15$ and $35$ share factor $5$
• All four numbers are in one component.

Checking all pairs is $O(n^2)$. Can you do better? Constraints: up to $2 \cdot 10^4$ numbers, each up to $10^5$.