Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的

数对(x,y)有多少对.

 

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

 

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

/*    根据gcd(x,y)=p，得到gcd(x/p,y/p)=1     先枚举所有素数p，然后枚举p的倍数x，利用欧拉函数求出y的个数。    直接计算欧拉函数会超时，可以预处理出来。 */#include
      
       #include
       
        #define N 10000010using namespace std;int prime[N],f[N],euler[N],n,num;void get_prime(){    for(int i=2;i<=n;i++){        if(!f[i]) prime[++num]=i;        for(int j=1;j<=num;j++){            if(i*prime[j]>n) break;            f[prime[j]*i]=1;            if(i%prime[j]==0) break;        }    }}void get_euler(){    for(int i=1;i<=n;i++) euler[i]=i;    for(int i=2;i<=n;i++){        if(euler[i]==i){            for(int j=i;j<=n;j+=i)                euler[j]=euler[j]/i*(i-1);        }    }}int oula(int x){    int ans=x;    for(int i=2;i*i<=x;i++){        if(x%i==0){            ans-=ans/i;            while(x%i==0) x/=i;        }    }    if(x>1) ans-=ans/x;    return ans;}int main(){    scanf("%d",&n);    get_prime();get_euler();    long long ans=0;    for(int i=1;i<=num;i++){        int p=prime[i];long long tot=0;        for(int j=p;j<=n;j+=p)            tot+=(long long)euler[j/p];        ans+=tot*2-1;    }    cout<