Count coprime integers
For , the Euler totient function counts the integers satisfying . In particular, .
Number Theory
Euler's Totient Function
Euler's Totient Function
- Назария
- Дарси 1 аз 1
- Хониш: 5 дақиқа
Euler's Totient Function
For , the Euler totient function counts the integers satisfying . In particular, .
For a prime , all integers from to are coprime to it, so . For a prime power, only multiples of are excluded:
An integer is coprime to exactly when none of the prime divisors of divides it.
For each prime divisor , exclude its multiples. Inclusion–exclusion handles overlaps: for any chosen set of distinct prime divisors, their product divides , so exactly divided by that product integers are multiples of all of them.
Expanding the inclusion–exclusion sum gives
The product includes each distinct prime only once. Compute its contribution with the integer update
starting from . Earlier updates divide only by other primes, so still divides the current answer.
For positive coprime , their prime-factor sets are disjoint. The same formula therefore gives
For the original input , this takes time and extra memory.
Initialize . Process candidates in increasing order. If , then is prime: every composite has already been reduced by a smaller prime factor.
Apply to every multiple of , starting at itself. This includes the update .
Call for . Afterward, for ; entry zero is unused. Each call rebuilds the table.
The sieve takes time and memory. Each later query is a table lookup taking time.
For each divisor of , group the integers satisfying .
Write . Then and , so this group contains integers. The groups partition all integers, giving
For an interval with , maintain an answer and a remaining value for each in the interval.
The final remainder is prime because the base-prime list covers every possible small factor. Each distinct prime contributes exactly once, so .
Begin visiting multiples at . Include itself when it lies in the interval, since its totient also needs that prime's contribution.
The two interval arrays use memory, where . Preparing the base primes with a sieve adds memory.
#include <bits/stdc++.h>
using namespace std;
long long phi(long long n) {
long long res = n;
for (long long p = 2; p <= n / p; p += (p == 2 ? 1 : 2)) {
if (n % p == 0) {
res -= res / p;
while (n % p == 0) {
n /= p;
}
}
}
if (n > 1) {
res -= res / n;
}
return res;
}
vector<int> t;
void phi_sieve(int n) {
t.resize(n + 1);
for (int x = 0; x <= n; x++) {
t[x] = x;
}
for (int p = 2; p <= n; p++) {
if (t[p] != p) {
continue;
}
for (int x = p; x <= n; x += p) {
t[x] -= t[x] / p;
}
}
}