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(a,b)=p 则 gcd(a/p,b/p)=1;

设 a<=b 则gcd(a,b)=phi[b]（与b互质的个数）

所以只需要枚举每一个素数，每一个数（这里可以用n的前缀和来维护，记为f[n]）求解出ans=Σf[n/prime[i]]*2-1(考虑a>b，并减去(1,1)之类的值)

1 #include
      
        2 const int maxn=10000010; 3 bool pd[maxn]; 4 long long phi[maxn],prime[maxn],top,n,ans; 5 void ES(){ 6     for(int i=2;i