easy,but 100ac

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MaxN = 10000100;
int n, tot, check[MaxN], prime[MaxN];
ll ans, phi[MaxN];

int main(){
    scanf("%d",&n);

    phi[1] = 1ll;
    for(int i = 2; i <= n; i++){
        if (!check[i]) { phi[i] = i - 1; prime[++tot] = i; }
        for (int j = 1; j <= tot; j++){
            if (i * prime[j] > n) break;
            check[i * prime[j]] = 1;
            if (i % prime[j] == 0){ phi[i * prime[j]] = phi[i] * prime[j]; break; }
            else { phi[i * prime[j]] = phi[i] * (prime[j] - 1); }
        }
    }
    for(int i = 1; i <= n; i++) phi[i] += phi[i-1];

    for(int i = 1; i <= tot; i++) ans += phi[n / prime[i]];
    printf("%lld\n", ans * 2 - tot);    
    return 0;    
}