I think the Hall Marriage Theorem will give you necessary and sufficient conditions for the existence of a coupling:
Write $i\sim j$ if $i/\gcd(i,j)$ is prime or $i=j$.
Define functions:
\begin{align*}
a\colon\mathcal P(B)\to\mathcal P(A);
&\quad a(T)=\{i\in A\colon \exists j\in T\text{ with }i\sim j\}\text{; and}\\
b\colon \mathcal P(A)\to \mathcal P(B);
&\quad b(S)=\{j\in B\colon \exists i\in S\text{ with }i\sim j\}.
\end{align*}
There are two equivalent necessary and sufficient conditions.
For each $S\subseteq\{1,\ldots,n\}$, you require
$\mathbb P(B\in b(S))\ge \mathbb P(A\in S)$; OR
for each $T\subseteq \mathbb N$, you require $\mathbb P(A\in a(T))\ge \mathbb P(B\in T)$.
NB: In your situation, of course it's much easier to check the first condition, as there are only finitely many $S$'s to check.
EDIT (based on question in comments)
You asked whether the Hall Marriage theorem applies given that $B$ takes values in an infinite set. I guess the strict answer is no, but an extension of the theorem does apply. One very useful fact is that the collection of couplings of a pair of discrete random variables forms a compact set (in fact the result is more general than this), where the distance between a pair of couplings is just the sum of the absolute values of the difference in the probability of $(i,j)$.
First, let's show that the conditions are necessary. Suppose that there is a coupling satisfying your condition. This implies that $\mathbb P(B\in b(A))=1$. Now we have $\mathbb P(B\in b(S))\ge\mathbb P(A\in S,B\in b(S))=\mathbb P(A\in S)$. Similarly $\mathbb P(A\in a(T))\ge
\mathbb P(A\in a(T),B\in T)=\mathbb P(B\in T)$.
We will use compactness for the sufficiency. Let $\epsilon>0$. Then there exists an $M$ such that $\mathbb P(B\in b(S)\cap \{1,\ldots,M\})\ge (1-\epsilon)\mathbb P(A\in S)$ for each of the finitely many subsets $S$ of $\{1,\ldots,n\}$. Hall's theorem gives a sub-coupling: a measure on $\{1,\ldots,n\}\times \{1,\ldots,M\}$ where the $i$th row sums to at least $(1-\epsilon)\mathbb P(A=i)$ satisfying the constraint. We can then use compactness to take a limit, which will be a true coupling (since each row sums to the correct thing).
If the other condition is satisfied, you have $\mathbb P(A\in a(T))\ge \mathbb P(B\in T)$ for each subset $T$ of $\{1,\ldots,M\}$. This allows you to construct a sub-coupling on $\{1,\ldots,n\}\times\{1,\ldots,M\}$ where each column sums to $\mathbb P(B=j)$. Taking a limit of these, again, you obtain a true coupling.
