给定整数 $N$，求 $1≤x,y≤N$ 且 $GCD(x,y)$ 为素数的数对 $(x,y)$有多少对。

$GCD(x,y)$即求 $x，y$的最大公约数。

输入格式

输入一个整数 $N$。

输出格式

输出一个整数，表示满足条件的数对数量。

数据范围

$1≤N≤10^7$

输入样例：

4

输出样例：

4

#include <iostream>

using namespace std;

const int N = 1e7 + 10, mod = 1e9 + 7;

int n, cnt, p[N], phi[N];
long long s[N], res;
bool v[N];

int main()
{
    cin >> n;
    for (int i = 2; i <= n; i ++ )
    {
        if (!v[i])
        {
            p[cnt ++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; p[j] * i <= n; j ++ )
        {
            v[p[j] * i] = 1;
            if (i % p[j] == 0)
            {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + phi[i];
    for (int i = 0; i < cnt; i ++ ) res += s[n / p[i]] * 2 + 1;
    cout << res;

    return 0;
}