Euler Phi + Sieve

#include <bits/stdc++.h>
using namespace std;

const int maxN = 151622;
int64_t isVisited[maxN / 64 + 200];
vector<int64_t> primes;
void Sieve_of_Eratosthenes(int limit){
    limit += 100;
    for(int64_t i = 3; i <= sqrt(limit) ; i += 2){
        if(!(isVisited[i/64]&(1LL<<(i%64)))) {
            for(int64_t j = i * i; j <= limit; j += 2 * i) {
                isVisited[j/64] |= (1LL<<(j%64));
            }
        }
    }
    primes.push_back(2);
    for(int64_t i = 3; i <= limit; i += 2){
        if(!(isVisited[i / 64] & (1LL << (i % 64)))) {
            primes.push_back(i);
        }
    }
}

int64_t Phi (int64_t n) {
    if (n == 1) return 0;
    int64_t res = n;
    for (int64_t i : primes) {
        if (i * i > n) break;
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res -= res / i;
        }
    }
    if (n != 1) {
        res -= res / n;
    }
    return res;
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     Sieve_of_Eratosthenes(maxN);
     for (int test_case = 1; test_case <= T; ++test_case) {
         int64_t n;
         while (cin >> n and n > 0) {
             cout << Phi(n) << '\n';
         }
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}