Examples
Properties
The following three properties will allow us to calculate it for any number:
- if
is a prime then
Proof: obviously since
- if
is a prime and a positive integer then
Proof: Since the multiples of
Example:
multiples of
- if
and are relatively prime then
Proof: TODO, read the chinese remainder theorem
Computation
Given a number
Applying the euler function we get:
Implementation
Time complexity:
int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i += 1) {
// if `i` is a divisor of `n`
if (n % i == 0) {
// divide it by `i^k` so that it's no longer divisible by `i`
while (n % i == 0) {
n /= i;
}
// all the multiples of `i` are coprime to n, the number of
// multiples is equal to `i * k` <= n, therefore `k <= n / i`
result -= result / i;
}
}
if (n > 1) {
result -= result / n;
}
return result;
}
Problems
10179 - Irreducable Basic Fractions 10299 - Relatives 11327 - Enumerating Rational Numbers