题目链接：

题目分类：

题意：

给定整数n，求x和y都在1到n之间且gcd(x,y)为素数的数对有多少对。

题解：

可以考虑枚举gcd(x,y)的值，然后问题变成在一个范围内的互质的数对有多少对。

这个可以使用phi函数的前缀和完成。

程序：

#include<cstdio>
using namespace std;
bool isp[12000000];
int n;
int phi[12000000];
int mi[12000000];
long long f[12000000];
inline int min(int x,int y)
{
	if(x<y)return x;
	return y;
}
inline void shai()
{
	for (int i=1;i<=n;i++)mi[i]=100000000;
	for (int i=2;i<=n;i++)
	{
		if(isp[i]==0)
		{
			mi[i]=i;
			for (int j=i+i;j<=n;j+=i)
			{
				isp[j]=1;
				mi[j]=min(mi[j],i);
			}
		}
	}
}
inline void getphi()
{
	phi[1]=1;
	for (int i=2;i<=n;i++)
	{
		if((i/mi[i])%mi[i]==0)
		{
			phi[i]=phi[i/mi[i]]*mi[i];
		}
		else
		{
			phi[i]=phi[i/mi[i]]*(mi[i]-1);
		}
	}
	f[1]=1LL;
	for (int i=2;i<=n;i++)
	{
		f[i]=f[i-1]+((long long)phi[i])*2LL;
	}
}
inline long long getans()
{
//	for (int i=1;i<=n;i++)printf("%d ",phi[i]);
	long long ans=0;
	for (int i=2;i<=n;i++)
	{
		if(isp[i]==0)
		{
			ans+=(long long)f[n/i];
		}
	}return ans;
}
int main()
{
	scanf("%d",&n);
	shai();
	getphi();
	printf("%lld\n",getans());
	return 0;
}