Untitled

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int kMaxN = 1e8;

vector<int> phi(kMaxN + 1, 0);

void CalcPhi2() {
    phi[1] = 1;
    for (int n = 2; n <= kMaxN; ++n) {
        if (phi[n] != 0) continue;
        long long diff = n - 1;
        for (long long p = n; p <= kMaxN; p *= n) {
            for (int c = 0; c * p * n <= kMaxN; ++c) {
                long long val = c * p * n;
                for (int k = 1; k < n && p * (c * n + k) <= kMaxN; ++k) {
                    if (phi[c * n + k] == 0) continue;
                    phi[val + p * k] = phi[c * n + k] * diff;
                }
            }
            diff *= n;
        }
    }
}

void CalcPhi3() {
    phi[1] = 1;
    for (int n = 2; n <= kMaxN; ++n) {
        if (phi[n] != 0) continue;
        int diff = n - 1;
        for (long long p = n; p <= kMaxN; p *= n) {
            for (int c = 1; c * p <= kMaxN; c++) {
                int val = c * p;
                if (phi[c] == 0) continue;
                phi[val] = diff * phi[c];
            }
            diff *= n;
        }
    }
}

int main()
{

    auto start = high_resolution_clock::now();
    CalcPhi3();
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    int n;
    cin >> n;
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += phi[i];
        if (i % 100 == 0) {
            sum = 0;
        }
    }
    if (sum != 0) {
        cout << sum << " ";
    }
    cout << endl;
    cout << "Time taken by function: " << duration.count() / 1000000. << " seconds" << endl;
    return 0;
}