Count ordered pairs $i$,$j$ for the following $\sum_{i=1}^M\sum_{j=1}^N \text{isPrime}(\gcd(i,j))$ Given $M$,$N$ we are to find $\sum_{i=1}^M\sum_{j=1}^N \text{isPrime}(\gcd(i,j))$
where $\text{isPrime}(X)=1$ if $X$ is prime, $0$ otherwise.
My thoughts are in the direction to somehow extend/generalize the solution to count of number of pairs of coprime as I stumbled upon that problem earlier

*

*How many coprime ordered pairs are there up to $N$?


*Number of ordered pairs of coprime integers from $1$ to $N$


*Efficient way to compute $\sum_{i=1}^n \varphi(i) $
 A: The original sum is equal to
\begin{aligned}
\sum_p\mathop{\sum_{i\le M}\sum_{j\le N}}_{(i,j)=p}1
&=\sum_p\sum_{u\le M/p}\sum_{\substack{v\le N/p\\(u,v)=1}}1=\sum_p\sum_{u\le M/p}\sum_{t|u}\mu(t)\left\lfloor N\over pt\right\rfloor \\
&=\sum_p\sum_{t\le M/p}\mu(t)\left\lfloor N\over pt\right\rfloor\sum_{\substack{u\le M/p\\t|u}}1=\sum_p\sum_{t\le M/p}\mu(t)\left\lfloor N\over pt\right\rfloor\left\lfloor M\over pt\right\rfloor \\
&=\sum_{p\le\min(M,N)}\sum_{t\le\min(M,N)/p}\mu(t)\left\lfloor N\over pt\right\rfloor\left\lfloor M\over pt\right\rfloor \\
&=\sum_{t\le\min(M,N)}\mu(t)\sum_{p\le\min(M,N)/t}\left\lfloor N\over pt\right\rfloor\left\lfloor M\over pt\right\rfloor,
\end{aligned}
where the second inequality follows from the fact that
$$
\sum_{\substack{n\in S\\(n,q)=1}}1=\sum_{n\in S}\sum_{d|(n,q)}\mu(d)=\sum_{d|q}\mu(d)\sum_{\substack{n\in S\\ q|n}}1.
$$
A: After some manipulations I got
$$\sum_{i=1}^m\sum_{j=1}^n \chi_{\Bbb P}(\gcd(i,j)) = \sum_{k=1}^{\min(m,n)}\left\lfloor\frac{m}{k}\right\rfloor \left\lfloor\frac{n}{k}\right\rfloor\sum_{p\mid k}\mu(k/p)$$
