Why this matters when you build with AI
Ask an AI tool for Euler's totient and it often writes a loop from 1 to n that calls gcd on each number. That answer is correct, and it is also slow when you call it for many values: each call costs about n steps, so 10^5 calls with n near 10^6 means about 10^11 steps. The fast version uses the prime factors of n and needs about the square root of n steps for one value.
The second common problem is a silent overflow. Many tools write the formula as n * (p - 1) / p. For a prime near 10^12 the product n * (p - 1) is near 10^24, which is far above the 64-bit limit of about 9.2 * 10^18, so the answer is wrong and no error is printed. The fix is to divide first, as this lesson shows.
The third problem is a sieve bug. A sieve for totients looks like a sieve for primes, and it is easy to drop the check that tells a prime from a composite number. The output then looks plausible and is wrong for some inputs, as the mistakes section shows.
Two terms first. Two numbers are coprime when their greatest common divisor is 1, which means they share no prime factor. Euler's totient of n, written phi(n) or phi(n) in code, is the number of integers k from 1 to n that are coprime with n. For n = 8 the coprime numbers are 1, 3, 5 and 7, so phi(8) = 4.
The idea: count the numbers coprime with n
Start with primes and prime powers, because the rest is built from them.
If p is a prime, every number from 1 to p - 1 is coprime with p, so phi(p) = p - 1. For example phi(7) = 6, since 1 through 6 all share no factor with 7.
If p is a prime and k is at least 1, then phi(p^k) = p^k - p^(k-1). The only numbers from 1 to p^k that are not coprime with p^k are the multiples of p, and there are p^(k-1) of them. For 8 = 2^3 this gives 8 - 4 = 4, which matches the list 1, 3, 5, 7.
The third rule is the one that makes the whole thing work. If m and n are coprime, then phi(m * n) = phi(m) * phi(n). This is called multiplicativity. Take m = 3 and n = 5. The totient of 15 is 2 * 4 = 8, and the list of numbers from 1 to 15 coprime with 15 is 1, 2, 4, 7, 8, 11, 13 and 14, which has 8 entries.
Put these together and you get the formula that is used in code. Let p1, p2, ..., pr be the distinct primes that divide n. Then
phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr).
The reason is inclusion and exclusion. Start with the n numbers from 1 to n. Remove the multiples of each prime, then add back the multiples of each pair of primes that were removed twice, and so on. Each prime contributes a factor of (1 - 1/p), which is the share of numbers that survive it.
A worked example: phi(36)
The number 36 is 2^2 * 3^2, so its distinct primes are 2 and 3. The formula gives
phi(36) = 36 * (1 - 1/2) * (1 - 1/3) = 36 * (1/2) * (2/3) = 12.
Check it by listing: the numbers from 1 to 36 that are coprime with 36 are 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31 and 35. There are 12 of them. Note that the formula does not need the powers of the primes, only the distinct primes.
Keeping the arithmetic in integers
The formula has fractions, but the answer is always an integer. In code, multiply and divide in an order that keeps every intermediate value a whole number. Start with result = n. For each distinct prime p, replace result with result / p * (p - 1). This is result * (1 - 1/p) written without fractions.
The division is exact. When p is processed, result still contains the factor p. Every earlier step only multiplied by (q - 1) and divided by a different prime q, so p still divides result. For the same reason, result / p * (p - 1) never overflows when the true answer fits, because result is never larger than n.
Computing phi for one value
Trial division finds the distinct primes of n by testing each candidate up to the square root of n. Once a prime p is found, remove every copy of it from n so that p is not found again, and apply the factor (1 - 1/p) to the result.
// phi(n) by trial division, O(sqrt n).
ll phi_one(ll n) {
ll result = n;
for (ll p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p; // strip every copy of p
result = result / p * (p - 1); // result * (1 - 1/p), divide first
}
}
if (n > 1) result = result / n * (n - 1); // one prime factor left, larger than sqrt
return result;
}Trace it on n = 36. The result starts at 36. At p = 2, the loop removes both factors of 2, which leaves n = 9, and the result becomes 36 / 2 * 1 = 18. At p = 3, the loop removes both factors of 3, which leaves n = 1, and the result becomes 18 / 3 * 2 = 12. The loop stops because 4 * 4 is larger than 1, and the final if does nothing because n is 1. The function returns 12.
The last if handles a prime factor larger than the square root. For n = 46 = 2 * 23 the loop checks p = 2 and then stops at p = 5, because 5 * 5 = 25 is larger than the remaining n = 23. The leftover 23 is prime, and the final step gives 46 / 2 * 1 = 23, then 23 / 23 * 22 = 22.
The same idea in Python is short. It is fast enough for a few single values up to about 10^12, which needs at most a million loop steps.
def phi_one(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result = result // p * (p - 1)
p += 1
if n > 1:
result = result // n * (n - 1)
return resultFor a single value the cost is O(sqrt n), so this is the right tool when you ask for a few values. It is the wrong tool for a million values, and the next section covers that case.
Computing phi for every value up to n with a sieve
A sieve writes the answer for many numbers at once. Start with phi[i] = i for every i. Then go through the numbers in increasing order. When phi[p] == p at some p, p is a prime, because a composite number would have been reduced by its smaller prime factors earlier. For each multiple j of p, apply the factor (1 - 1/p) with phi[j] -= phi[j] / p. This is the same as phi[j] = phi[j] / p * (p - 1), written as a subtraction.
Trace it for n = 12. Start with 1 through 12. After p = 2, the even numbers are halved: phi[2] = 1, phi[4] = 2, phi[6] = 3, phi[8] = 4, phi[10] = 5, phi[12] = 6. After p = 3, the multiples of 3 are changed: phi[3] = 2, phi[6] = 3 - 1 = 2, phi[9] = 6, phi[12] = 6 - 2 = 4. After p = 5, phi[5] = 4 and phi[10] = 5 - 1 = 4. After p = 7 and p = 11, the values phi[7] = 6 and phi[11] = 10 are set. The final list for 1 to 12 is 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4.
// phi(i) for every i in [0, n] with a sieve, O(n log log n).
vector<int> phi_sieve(int n) {
vector<int> phi(n + 1);
for (int i = 0; i <= n; ++i) phi[i] = i;
for (int p = 2; p <= n; ++p) {
if (phi[p] == p) { // p is prime: no smaller prime has touched it
for (int j = p; j <= n; j += p)
phi[j] -= phi[j] / p; // multiply by (1 - 1/p) once per prime p
}
}
return phi;
}Why is phi[j] / p exact? When p is processed, phi[j] still has a factor p, for the same reason as in the single-value code: the earlier primes were removed from j, but p was not. So the subtraction always gives the integer phi[j] * (1 - 1/p).
The running time is the sum of n / p over the primes p up to n. That sum is about n log log n, which is close to linear for every n you will meet in a contest. The vector holds int values, so for n up to about 2 * 10^9 the values fit in 32 bits, and the array takes 4 bytes per number.
A linear sieve, which is covered in the sieves lesson, can also compute phi for all values in O(n). This lesson uses the classic version because the check phi[p] == p shows the reason for each step.
The identity: the totients of the divisors add up to n
One more fact makes many counting problems easy. For every n,
the sum of phi(d) over all divisors d of n equals n.
Take n = 12. Its divisors are 1, 2, 3, 4, 6 and 12, and their totients are 1, 1, 2, 2, 2 and 4. The sum is 12.
The reason is a grouping argument. Sort the numbers 1 to n by their gcd with n. For each divisor d of n, the numbers k with gcd(k, n) = d are exactly the numbers d * j where j runs from 1 to n / d and j is coprime with n / d. There are phi(n / d) such j, so the group for d has phi(n / d) numbers. Every number from 1 to n lands in exactly one group, so the group sizes add up to n. As d runs over the divisors of n, so does n / d, which gives the identity.
Check this with code when you use it. The check program used while writing this lesson, which is not part of the exercise, tests the identity for every n up to 3000 and compares phi_one, phi_sieve and a brute force loop for the same range.
Worked example: count pairs with 2p < q
Here is a problem written for this lesson.
Input: one integer N with 1 <= N <= 10^7. Count the pairs (p, q) of integers such that 1 <= p <= N, 1 <= q <= N, gcd(p, q) = 1 and 2p < q. Print the count.
Start with a brute force, which tries every pair. For N = 10 it counts 15 pairs. A brute force loops over all pairs, so it takes about N^2 gcd calls. That is too slow for N = 10^7, so we need the totient.
Fix q. Count the numbers p with gcd(p, q) = 1 and 2p < q. For q = 1 and q = 2 there is no such p, since 2p < 2 needs p < 1. For q >= 3 there is a neat symmetry. The numbers p from 1 to q - 1 that are coprime with q number phi(q). Replace p by q - p. This maps the coprime numbers to coprime numbers, because gcd(q - p, q) = gcd(p, q). It swaps the numbers below q/2 with the numbers above q/2. The number q/2 itself is never coprime with q when q >= 3, because then q/2 divides q. So exactly half of the coprime numbers are below q/2, and that half is phi(q) / 2. Note that phi(q) is even when q >= 3, so the division is exact.
The answer is therefore the sum of phi(q) / 2 for q from 3 to N. Here is the full solution.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// phi_sieve as defined above
vector<int> phi_sieve(int n);
// Count pairs (p, q) with 1 <= p, q <= N, gcd(p, q) = 1 and 2p < q.
// Solution: sum of phi(q) / 2 over q = 3..N.
int main() {
int N;
cin >> N;
vector<int> phi = phi_sieve(N);
ll answer = 0;
for (int q = 3; q <= N; ++q) answer += phi[q] / 2; // phi(q) is even for q >= 3
cout << answer << "\n";
}The sieve gives every phi(q) up to N in O(N log log N) time. The sum is accumulated in a long long, because the answer for N = 10^7 is about 1.5 * 10^13, which does not fit in a 32-bit int.
The program was compiled with g++ -O2 -std=c++17 -Wall -Wextra using g++ 15.2.0 on Linux. Its output for N = 10 is:
15The brute force program prints the same 15 for N = 10. On 240 values of N, from 1 to 120 and 120 random values from 121 to 400, the two programs printed the same answer every time. For N = 1000 both print 152095. The same program on N = 10^7 printed 15198178213620 in about 1.1 seconds of wall time on the machine used here, which is a WSL2 Linux system. Your time will differ.
Hands-on exercise
Work through these steps in a scratch folder on your own machine.
First, write the brute force. It should loop over p and q, call gcd from the standard library, and count the pairs with 2 * p < q. Keep it short, because its only job is to be correct.
Second, write the fast solution above. Compile both with g++ -O2 -std=c++17. Feed both the same 200 random values of N between 1 and 300, and compare the outputs. Keep the random seed fixed, so that a failure can be repeated.
Third, change the property and check the result by hand. Count pairs with p <= q instead of 2 * p < q. For N = 10 the answer should be 32, which is the sum of phi(1) through phi(10). If your program prints 31, phi(1) was set to 0 somewhere.
Fourth, time N = 10^7 and record the number. Do not expect the same number as this lesson, because the time depends on the machine.
A good answer prints the same numbers as the brute force on every test, gives 32 for the variant with N = 10, and runs N = 10^7 in a few seconds. Check the formula by listing the coprime numbers for a small q, such as q = 12, where phi(12) = 4 and the coprime numbers are 1, 5, 7 and 11.
Prompt to try with an AI tool
Use this prompt, then check the answer with the brute force above:
Write a C++17 program that reads one integer N, 1 <= N <= 10^7, and prints the sum of
Euler's totient phi(q) for q from 1 to N. Use a sieve and a long long for the sum.
Explain in two sentences why the sum needs 64 bits. Then give the output for N = 10.A good answer uses a sieve that starts with phi[i] = i and reduces the multiples of each prime p, gives the output 32 for N = 10, and uses long long for the sum. Check that the code does not set phi(1) to 0, and that the sieve checks for a prime before reducing the multiples.
Complexity
For a single value, trial division takes O(sqrt n) time and O(1) memory. For all values up to n, the sieve takes O(n log log n) time and O(n) memory, with 4 bytes per value when the values are stored as int. The counting program takes O(N log log N) time for the whole exercise, and its answer fits in a long long for N up to 10^7.
Common mistakes
These are the mistakes that show up most often, with the real output each one produced in the tests for this lesson.
The first mistake is setting phi(1) to 0. The number 1 is coprime with itself, so phi(1) = 1. A sum of phi(1) through phi(10) with phi(1) = 0 prints 31 instead of 32. The symptom is an answer that is one smaller than expected for every N, which is easy to miss if you only check large inputs.
The second mistake is multiplying before dividing. The line result = result * (p - 1) / p gives a wrong answer for a large prime. For the prime 999999999989, the correct value of phi is 999999999988. The version that multiplies first printed 2003741 in the test, because result * (p - 1) overflowed a 64-bit integer. The version that divides first printed 999999999988. The symptom is a wrong number with no warning, so compare large inputs with the single-value function on a second, simpler method.
The third mistake is dropping the prime check in the sieve. If the loop reduces the multiples of every i, not only the primes, the output for n = 12 is 1, 1, 2, 2, 4, 2, 6, 3, 6, 4, 10, 3. The values phi(8) and phi(12) are 3, but the correct values are 4 and 4. The reason is that 2 is applied twice to 8, once for the prime 2 and again for the composite 4, so phi(8) is 8 * (1/2) * (3/4) = 3.
The fourth mistake is an int accumulator for the sum. For N = 10^7 the sum needs about 1.5 * 10^13. An int accumulator printed -1711046924 in the test, because the value wrapped around. Use long long for every sum over totients.
The fifth mistake is applying the formula to the wrong primes. The product uses each distinct prime once. If the code keeps the repeated factors, as in result * (p - 1) / p run for every copy of p, the answer is too small. For 36, using the prime 2 twice gives 36 * (1/2) * (1/2) * (2/3), which is 6 by hand, not 12.
A prompt to check AI output
When an AI tool gives you a totient function, ask it to explain its own check:
For the function you wrote, list phi(1), phi(2), phi(12), phi(36) and phi(10^9 + 7) with a
one-line reason for each. Then say which line divides by a prime, and why that division
is exact. Do not change the code.A good answer gives 1, 1, 4, 12 and 1000000006, and explains that p divides the current result at the moment of division. Check each value by hand or with the brute force. If the tool gives phi(1) = 0, or does its division after the multiplication, do not use the code.
Checklist
- phi(n) counts the k from 1 to n with gcd(k, n) = 1, and phi(1) = 1.
- phi(p^k) = p^k - p^(k-1) for a prime p, and phi is multiplicative for coprime parts.
- For one value, use trial division, remove every copy of each prime, and divide before multiplying.
- For many values, start with
phi[i] = iand reduce the multiples of each prime p, checkingphi[p] == pfirst. - Store the sum of totients in a
long long. - Test the function against a brute force loop for every n up to a few thousand, and compare one large value with a second method.
Practice
These take a few minutes each. Try them on paper or in your scratch folder before opening the answers.
Practice 1: phi(360) by hand
Find phi(360) with the product formula.
Hint: Write 360 as a product of prime powers first.
Show the answer
360 = 2^3 * 3^2 * 5, so phi(360) = 360 * (1/2) * (2/3) * (4/5) = 96. The code above prints 96 for this input.
Practice 2: the divisor identity for 12
List the divisors of 12, find each totient, and check that they add up to 12.
Hint: The divisors of 12 are 1, 2, 3, 4, 6 and 12.
Show the answer
The totients are 1, 1, 2, 2, 2 and 4, and their sum is 12, as the identity says.
Practice 3: which n have phi(n) = 4
List every n with phi(n) = 4.
Hint: Use the formula to check the candidates 5, 8, 10 and 12 and rule out the rest by a short argument, or check each n from 1 to 200 with a loop.
Show the answer
The values are n = 5, 8, 10 and 12. A check of every n from 1 to 199 with a brute force loop finds exactly these four.
Practice 4: which n have phi(n) = n / 2
Find every n with phi(n) = n / 2. Then count how many such n are at most 10^6.
Hint: Write phi(n) / n as a product of (1 - 1/p) over the distinct primes p, and ask which set of primes gives exactly 1/2.
Show the answer
The answer is the powers of 2 from 2 upward, n = 2^k with k at least 1. Here is why. Let S be the set of distinct primes of n. Then phi(n) / n = product over p in S of (p - 1)/p, and this equals 1/2. Multiply both sides by 2 times the product of the primes in S to get 2 * product of (p - 1) = product of p. If 2 is not in S, the left side is even and the right side is odd, which is impossible. So 2 is in S, and cancelling the factor 2 gives product of (p - 1) over the odd primes in S = product of the odd primes in S. Each p - 1 is smaller than p, so the two products can only be equal when there are no odd primes. The set S is . The powers of 2 at most 10^6 are 2^1 through 2^19, since 2^19 = 524288 and 2^20 is above 10^6. That gives 19 numbers. The brute force check up to 3000 lists 2, 4, 8, ..., 2048, which matches.
Practice 5: why the sum overflows in 32 bits
The sum of phi(q) / 2 for q up to 10^7 is about 1.5 * 10^13. Explain in two sentences what goes wrong if the accumulator is an int, and what the fix is.
Hint: A 32-bit signed integer holds values up to about 2.1 * 10^9.
Show the answer
The sum is far above 2^31 - 1, so an int wraps around and prints a wrong value, for example -1711046924 in the test run above. Use long long, which holds values up to about 9.2 * 10^18, for the total.
Summary
The totient of n is the count of numbers from 1 to n that share no prime factor with n. The count comes from the distinct primes of n through the product of (1 - 1/p), and the arithmetic stays in integers when you divide before you multiply. A sieve computes the totient of every value up to n in about n log log n steps. The totients of the divisors of n always add up to n, which gives counting problems a short solution once the totients are known.
Sources and scope
The definition of Euler's totient, its product formula, its multiplicativity and the divisor identity are standard results. Leonhard Euler studied the function in the 18th century. Carl Friedrich Gauss used the phi notation in Disquisitiones Arithmeticae, published in 1801. J. J. Sylvester coined the name "totient" in 1879. I checked these dates in an online encyclopedia summary and did not read the original books, and the sources disagree on the exact year of Euler's first use, so the dates are not given here.
The proofs in this lesson are short arguments written for this text: the inclusion and exclusion argument for the product, the grouping argument for the divisor identity, and the symmetry argument for the pair count. The claims about the programs come from runs on g++ 15.2.0 on Linux. Each program was compared with a brute force on random small inputs, and the outputs shown are the outputs of those runs. The running times depend on the machine and will differ on yours.