https://www.luogu.com.cn/problem/P2158
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 4e4 + 10; int v[maxn], phi[maxn], prime[maxn]; int n, m, ans; void euler() { m = 0; phi[1] = 1; for (int i = 2; i < n; i++) { if (!v[i]) v[i] = 1, prime[++m] = i, phi[i] = i - 1; for (int j = 1; j <= m && i * prime[j] < n; j++) { v[i * prime[j]] = 1; phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]); if (i % prime[j] == 0) break; } } } signed main() { //freopen("in","r",stdin); ios::sync_with_stdio(0); cin >> n; if(n == 1) cout << 0; else { euler(); ans = 0; for (int j = 2; j < n; j++) ans += phi[j]; cout << 2 * ans + 3 ; } return 0; }