Find if two numbers are linked by a greatest common divisor
That's an interesting problem. First of all, calculating directly the gcd between two numbers is clearly the fastest way to decide if they are connected. But as you noticed, quite unefficient for your problem.
A solution is to use prime factorization. Let's denote $P(z)$ the multiset prime factorization of a number $z$. Thus, you note that $gcd(x, y) = P(x) \cap P(y)$.
Once you have the prime factorization $P(x_0)$ of a number $x_0$, you may compute all sub-multisets (there are $2^k$ for $k$ primes values), and if the product $p$ of any sub-multiset is above $g$, any multiple of $p$ lesser than $n$ is connectected to $x_0$. Also note that all these multiples are a clique.
In fact, to generate all the connected numbers, you are only interested by &quot;irreductible&quot; sub-multisets. By irreductible, I mean that removing any (the smallest) prime factor would make the product lesser than $n$. Indeed, a reductible sub-multiset is already a multiple of an irreductible one and would generate no new connection. This may help to prune the loop on all sub-multisets of $x_0$.
Let's take a small example: $n = 100$, $g=10$, $x_0=60$.
$P(x_0) = \{2, 2, 3, 5\}$. The irreductible sub-multisets above $g$ are:

$P(12) = \{2, 2, 3\}$ =&gt; generating connections to $12 \times [1, 8]$
$P(15) = \{3, 5\}$ =&gt; generating connections to $15 \times [1, 6]$
$P(20) = \{2, 2, 5\}$ =&gt; generating connections to $20 \times [1, 5]$

Thus, we may generate the exhaustive list of the numbers conneted to $x_0$: $12, 24, 36, 48, 60, 72, 84, 96, 15, 30, 45, 75, 90, 20, 40, 80, 100$.
Also note that by construction you already have partially the prime factorization of all these numbers.
In your question, it is quite unclear of what may be the limits of ($n$, $g$). Or if your several ($x$, $y$) share the same ($n$, $g$). What I discussed until now is the fastest way I found to explore the graph of connections. But for very high ($n$, $g$), it may be unconvenient to list explicitely all connections of a number. If you do a BFS/DFS, an important point is that there is no point to explore again the clique of an irreductible multiset. In fact, I think I would try to do the BFS/DFS on the graph of these irreductible multiset instead of the graph of the number values.
Also remember that it may exist no path between $x$ and $y$. For example with $g = 20$ and $n = 80$, one may identify some connected components:

$\{31, 62\}$
$\{35, 70\}$
$\{21, 42, 63\}$
$\{25, 50, 75\}$