Description

给定整数 \(n\), 求 \(1 \leq x, y \leq n\) 且 \(gcd(x, y)\) 为素数的数对 \((x, y)\) 有多少对.

Input

输入只有一行一个整数 \(n\).

Output

输出题目要求的结果一行一个整数.

Sample Input

4

Sample Output

4

Data Range

对于所有数据, 满足:\(1 \leq n \leq 10^7\)

Explanation

题目要求的就是有多少个数对最大公约数为质数.

所以求的就是所有在范围内的质数有多少个互质的在范围内的倍数.

然后对于每一个质数加上对应的 \(\phi\) 函数就对了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 10000100;

int n;
int phi[maxn], prime[maxn];
bool vis[maxn];
lli res, sum[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Getting Euler function
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0]; j++) {
            int x = prime[j];
            if (i * x > n)
                break;
            vis[i * x] = true;
            if (i % x == 0) {
                phi[i * x] = phi[i] * x;
                break;
            } else {
                phi[i * x] = phi[i] * phi[x];
            }
        }
    }
    // Calculating
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
    for (int i = 1; i <= prime[0]; i++)
        res += sum[n / prime[i]] * 2 - 1;
    printf("%lld\n", res);
    return 0;
}