欧拉函数

ll get_euler(ll n)
{
    ll res = n;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            res = res * (i - 1) / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        res = res / n * (n - 1);
    return res;
}

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <stack>
#define FT(a, b) memset(a, b, sizeof(a))
#define FAT(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int t, prime[M], cnt, vis[M], euler[M];
ll get_euler(ll n)
{
    ll res = 1;
    euler[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime[cnt++] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; prime[j] <= n / i; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                euler[i * prime[j]] = euler[i] * prime[j];
                break;
            }
            euler[i * prime[j]] = euler[i] * (prime[j] - 1);
        }
        res += euler[i];
    }
    return res;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("/home/wjy/code/c++/in.txt", "r", stdin);
#endif
    ll n;
    scanf("%lld", &n);
    FAT(vis);
    cnt = 0;
    printf("%lld\n", get_euler(n));
    return 0;
}