题目让求有多少对$ 1\le x,y \le N$，满足$gcd(x,y)$是质数

即为$gcd(x,y)=d(d是质数)$

设$x=a*d,y=b*d(d是质数)$

即$\gcd(a*d,b*d)=d$

那么$x,y$可能的取值是$d,2*d,3*d…\frac{n}{d}*d$

得$a,b$的取值可能是$1,2,3…\frac{n}{d}$

在转换一下式子得:$gcd(a,b)=1$

所有我们只需要求从$1,2,3…\frac{n}{d}$中选出互质的数对的数量即可

显然就是欧拉函数的和的两倍(因为$(a,b)$和$(b,a)$实际算两次)

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e7+2019;
int prime[N],cnt;
int v[N],phi[N];
void euler(int n)
{
    memset(v,0,sizeof(v));
    cnt=0;
    phi[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(v[i]==0)
        {
            v[i]=i;prime[++cnt]=i;
            phi[i]=i-1;         
        }
        for(int j=1;j<=cnt;++j)
        {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
}
int n,ans;
int sum[N];
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>n;
    euler(n);
    for(int i=2;i<=n;++i) sum[i]=sum[i-1]+phi[i];
//    for(int i=1;i<=n;++i) cout<<sum[i]<<' ';
    for(int i=1;i<=cnt;++i)
    {
        int r=n/prime[i];
        ans+=sum[r]*2+1;
    }
     cout<<ans;
    return 0;
}