Problem Statement
Euler’s totient function φ(n) counts the number of integers
from 1 to n that are coprime to n. For example,
φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4.
Write a code to calculate the value of φ(n) for a given positive integer n.
Note that n is a value between 1 and 10^6.
Problem Solving Process
1. Understanding the Problem
This problem is based on the definition of Euler’s totient function,
and we need to find all the numbers that are coprime to n. Two numbers are
said to be coprime if their greatest common divisor is 1, and using this
condition we can calculate φ(n).
2. Algorithm Design
The Euler’s totient function can be expressed in the form of irreducible fractions. By this, we can find
the prime factors of n and calculate the number of coprime integers. For a prime factor p of n,
φ(n) = n × (1 – 1/p). We need to apply this formula for all prime factors of n.
3. Code Implementation
First, I will implement a function to find the prime factors, and then use it to
write the code to calculate φ(n).
def euler_totient(n):
result = n # Initial value is n
p = 2
while p * p <= n: # Finding prime factors
if n % p == 0: # Check if p is a prime factor of n
while n % p == 0: # Remove the prime factors corresponding to p
n //= p
result -= result // p # Calculate the number of coprimes
p += 1
if n > 1: # The last remaining prime factor
result -= result // n
return result
4. Examples and Tests
Let’s calculate φ(10). φ(10) has the prime factors 5 and 2.
Thus, φ(10) = 10 × (1 – 1/2) × (1 – 1/5) = 4.
print(euler_totient(10)) # Output: 4
5. Conclusion
Euler’s totient function is a very important concept in number theory,
providing essential knowledge for implementing advanced algorithms.
This problem helps establish this foundational knowledge.