Medium · Prime-Factor Product
Understand → Visualise → Practice.
Return the count of integers from 1 through n that are coprime with n.
φ(n) = n × ∏(1 − 1/p) over the distinct primes p dividing n. Find those primes by trial division up to √n.
result = n.
For each prime p dividing n, divide p out of n completely and set result −= result / p.
If n > 1 after the loop, it is a prime factor too: result −= result / n.
O(√n) time and O(1) space.
Applying the factor once per prime occurrence (e.g. twice for 2² ) is wrong; apply it once per distinct prime.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.