← all categories

Euler Phi a1aaf3e4

Euler's totient function phi(n) (count of integers in [1,n] coprime to n), single-query via trial division, or a sieve for all of [1, maxn).

Time: phi() O(\sqrt n); eulerPhiSieve() O(n \log\log n). tested

content/math/euler-phi.h

ll phi(ll n) {
    ll ans = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i) continue;
        while (n % i == 0) n /= i;
        ans -= ans / i;
    }
    if (n > 1) ans -= ans / n;
    return ans;
}

vector<ll> eulerPhiSieve(int maxn) {
    vector<ll> phi(maxn);
    iota(phi.begin(), phi.end(), 0);
    for (int i = 2; i < maxn; i++)
        if (phi[i] == i)  // i is prime
            for (int j = i; j < maxn; j += i) phi[j] -= phi[j] / i;
    return phi;
}