记所有不超过$n$的素数的集合为$Prime$
所求即为:$$\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)\in Prime$$
楼下大佬的莫反把我秀爆了,我来讲解一个简单的做法,且与秦淮岸不同.
不妨这样考虑:如果某对$gcd(i,j)=1$,那么他们乘上任意的$x\in Prime$,得到的$gcd(i\*x,j\*x)=x\in Prime$(当然,必须满足$i\*x,j\*x\le n$)
于是我们先求解$$\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)=1$$
显然这就是$$\sum_{i=1}^n2\times \varphi(i)+[i\in Prime]$$
($[i\in Prime]$当$i\in Prime$时为1,否则为0).
显然可以先欧拉筛在$O(n)$时间内求出这个式子(杜教筛:听说你要求欧拉函数前缀和?)
接下来我们只要考虑每对$gcd(i,j)=1$能和哪些(几个)$x$配对满足$i\*x,j\*x\le n$
考虑欧拉筛求出的素数是单调递增的,用二分可以在$O(nlogn)$的时间内解决.但是,如果从$2$到$n$枚举$i$,那么由于$i$递增,合法的$x$数量是递减的.可以用一个变量$it$维护当前的$i$最多能和几个$x$配对(显然是最小的$x$个),只要$p[it]*i>n$就不断减小$it$,最后$2\times \varphi(i)\times it$就是这个$i$的贡献(特别的,如果$i$是素数,那么$gcd(i,i)=i\in Prime$也有1的贡献).$it$至多扫一遍所有素数,所以变化是$O(n)$级别的.这样就可以在$O(n)$的时间内求解该问题.

/**********/省略快读
#define MAXN 1000011//数组开足
bool vis[MAXN];
ll p[MAXN/10],phi[MAXN],cnt=0;
void sieve(ll n)//欧拉筛求欧拉函数,O(n)
{
    vis[1]=1;
    phi[1]=0;
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i])
        {
            p[++cnt]=i;
            phi[i]=i-1;
        }
        for (int j = 1; j <= cnt && i*p[j] <= n ; ++j)
        {
            vis[i*p[j]]=1;
            phi[i*p[j]]=phi[i]*(p[j]-1);
            if (i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
        }
    }
}
int main()
{
    ll n=read(),ans=0;
    sieve(n);
    ll it=cnt;
    for (int i = 2; i <= n; ++i)
    {
        while (it&&i*p[it]>n)--it;//更新it
        ans+=2*phi[i]*it;//计算贡献
        if (!vis[i])++ans;
    }
    printf("%lld",ans);
    return 0;
}