Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$ I recently got asked the following question:

A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $g$. The number $n$ may be as large as $10^5$.
Alice has a list of $q$ cities that she'd like to visit. Given Alice's list of $q$ origin cities and $q$ destination cities, return a boolean vector with a 1 in the $i$th position indicating that it's possible to reach the $i$th destination city from the $i$th origin city, and 0 if not. The length of the list $q$ may be as large as $10^5$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $n$ and $q$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.
My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.
The fundamental question is whether there exists a faster than $O(n^2)$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $(i, j)$ for $1 \leq i,j \leq n$ needs to be looked at.
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.