证明：

当前数为质数时，ola[i] = i - 1，前面1 ~ i - 1所有数都与 i 互质

当前数不为质数时：

两种情况： i % prime[j] == 0 与 i % prime[j] != 0

① i % prime[j] == 0，此时 prime[j] 为 i 的最小质因子，则 prime[j] 也为 prime[j] * i的质因子

在计算中 ： ola[i * prime[j]] = i * prime[j] * (1 - 1 / p1) .... (1 - 1 / prime[j])

则当前已经包含了该质因子，对其进行化简得：ola[i * prime[j]] = ola[i] * prime[j]

② i % prime[j] != 0，此时，prime[j] 为 prime[j] * i 的质因子

计算时：ola[i * prime[j]] = i * prime[j] * (1 - 1 / p1) .... (1 - 1 / prime[j])

将 i与不包含prime[j] 的质因子合并，化简得：ola[i * prime[j]] = ola[i] * (prime[j] - 1)

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1000010;

int prime[N], cnt;
bool flag[N];
int n;
int ola[N];

LL get_ola()
{
    for(int i = 2; i <= n; ++i)
    {
        if(!flag[i])
        {
            prime[cnt++] = i;
            ola[i] = i - 1;
        }

        for(int j = 0; prime[j] <= n / i; ++j)
        {
            flag[prime[j] * i] = true;
            if(i % prime[j] == 0)
            {
                // 此时，说明prime[j] 为 i 的最小质数，则当前该数中的质数已经包含了prime[j]
                ola[i * prime[j]] = ola[i] * prime[j];

                break;
            }

            // 如果未跳出循环，则 prime[j] * i 的最小质数为 prime[j]，

            ola[i * prime[j]] = ola[i] * (prime[j] - 1);
        }
    }

    LL res = 1;
    for(int i = 2; i <= n; ++i) res += ola[i];

    return res;

}

int main()
{
    scanf("%d", &n);
    cout << get_ola() << endl;
    return 0;
}