令 $f(n)$ 为 $\gcd(a,b)=n$ 的正整数对 $(a,b)~(a\le N,b\le N)$ 的数量，不难发现

$f(n)=\lfloor\frac Nn\rfloor^2-\sum_{k=2}^{\lfloor\frac Nn\rfloor}f(k)$

最终输出为

$\sum_{\substack{p\in \mathbb P\\p\le N}}f(p)$

代码如下：

#include<iostream>
using namespace std;
const int N=1e7+4,M=1e6+4;
long long a[N];
int p[M];
bool f[N];
int main(){
	int n;
	cin>>n;
	for(int i=n;i>1;i--){
		long long v=n/i;
		v*=v;
		for(int j=i<<1;j<=n;j+=i){
			v-=a[j];
		}
		a[i]=v;
	}
	long long ans=0;
	int cnt=0;
	for(int i=2;i<=n;i++){
		if(!f[i]){
			p[cnt++]=i;
			ans+=a[i];
		}
		for(int j=0;j<cnt&&i*p[j]<=n;j++){
			f[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	cout<<ans;
}

该代码最劣点 $904\rm ms$，略微卡常后最劣点 $308\rm ms$，感觉不像 $O(N\log N)$ 的时间复杂度。