Contest1331/E.cpp

//
// Created by jal on 2019-05-01.
//

#include <bits/stdc++.h>
using namespace std;
vector<int>primes = {2,3,5};
vector<int>phi;
void init(int n){
    for(int i = primes.back()+2; i <= n; i+= 2){
        bool flag = true;
        for(auto p : primes){
            if(p * p > i)break;
            if(i % p == 0){
                flag = false;
                break;
            }
        }
        if(flag)primes.push_back(i);
    }
}
void genPhi(int max){
    int minDiv[max];
    for(int i = 1; i < max; i++){
        minDiv[i] = i;
    }
    for(int i = 2; i * i < max; i++){
        if(minDiv[i] == i){
            for(int j = i*i; j < max; j += i){
                minDiv[j] = i;
            }
        }
    }
    phi[1] = 1;
    for(int i = 2; i < max; i++){
        phi[i] = phi[i / minDiv[i]];
        if((i / minDiv[i]) % minDiv[i] == 0){
            phi[i] *= minDiv[i];
        }else{
            phi[i] *= minDiv[i] - 1;
        }
    }
}
int main(){
    int n;
    cin >> n;
    init(n);
    phi.resize(n+1);
    genPhi(n+1);
    vector<long long> sum(n/2+1, 0);
    for(int i = 1; i <= n/2; i++){
        sum[i] = sum[i-1] + phi[i];
    }
    long long cnt = 0;
    for(auto i : primes){
        cnt += phi[1];
        if(n / i != 1){
            cnt += 2 * (sum[n/i] - phi[1]);
        }
    }
    cout << cnt << endl;
}