本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

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

一个整数N

如题

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

1<=N<=10^7

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <string>

using namespace std;

typedef long long LL;

const int MAXN = 10000011;

const int MAXM = 5000011;

int n,phi[MAXN],prime[MAXM],cnt;

LL sum[MAXM],ans;

bool vis[MAXN];

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void work(){

	n=getint(); phi[1]=1; cnt=0; ans=0;

	for(int i=2;i<=n;i++) {

		if(!vis[i]) { phi[i]=i-1; prime[++cnt]=i; }

		for(int j=1;j<=cnt && ((LL)i*prime[j]<=n);j++) {

			vis[i*prime[j]]=1;

			//if(i%prime[j]==0) break;

			//并非积性函数

			if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; }

			else phi[i*prime[j]]=phi[i]*phi[prime[j]];

		}

	}

	for(int i=1;i<=5000000;i++) sum[i]=sum[i-1]+phi[i];

	for(int i=1;i<=cnt;i++) ans+=2*sum[n/prime[i]]-1;

	printf("%lld",ans);

}

int main()

{

    work();

    return 0;

}