Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$
Given parameters $n$ and $g$, you want to find the connected components of the graph on $[n] := \{1,\ldots,n\}$ whose edges are $\{(i,j) \in [n] : (i,j) &gt; g\}$. Let us write these edges in a different way:
$$
\bigcup_{d=g+1}^n \{(i,j) \in [n]: d \mid (i,j) \} =
\bigcup_{d=g+1}^n \{(dI,dJ) : 1 \leq I,J \leq n/d \}.
$$ 
For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path:
$$
\bigcup_{d=g+1}^n \{(dI,d(I+1)) : 1 \leq I &lt; \lfloor n/d \rfloor \}.
$$
The number of edges in the new graph is
$$
\sum_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum_{d=g+1}^n \frac{1}{d} = O(n\log n).
$$
You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.