题目链接：https://www.acwing.com/problem/content/description/222/

给定整数N，求1<=x,y<=N且GCD(x,y)为素数的数对(x,y)有多少对。

GCD(x,y)即求x，y的最大公约数。

输入格式

输入一个整数N

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

1≤N≤10^7

输入样例：

4

输出样例：

4

题解：

首先，用线性筛可以预处理处素数与欧拉函数。

我们定义 count(x）为： 1<=i,j<=N 有多少对gcd（i,j）=x;

那么原问题就转化成  （要求i是素数）

那么问题就转化成了，怎么能快速的求出count(x)

因为  count(x）为：1<=i,j<=N 有多少对gcd（i,j）=x ， 那么i和j必须是x的倍数，i和j的范围是x,2x,3x.....*x

那么我们把i和j都约掉一个x，那么约掉后的i和j要求i和j互质，那么问题就转化成:

1<=i,j<= ，有多少对数字两两互质。

那么很容易想到欧拉函数，euler(x) 是 1到x有多少对数字和x互质，然后用前缀和就可以预处出来

sum[1]=1,  sum[i]=sum[i-1]+2*euler[i]  

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+5;
int v[maxn],prime[maxn],cnt,phi[maxn];
ll sum[maxn];
void init(){
    for(int i=2;i<maxn;i++){
        if(!v[i]){
            prime[cnt++]=i;
            v[i]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt;j++){
            if(prime[j]>v[i]||prime[j]>maxn/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
    sum[1]=1;
    for(int i=2;i<maxn;i++) sum[i]=sum[i-1]+2*phi[i];
}
int main(){
    init();
    int n;
    cin>>n;
    ll ans=0;
    for(int i=2;i<=n;i++){
        if(v[i]==i){
            ans+=sum[n/i];
        }
    }
    cout<<ans<<endl;
    return 0;
}