Hello, everyone! Today I will explain in detail how to implement the Euler’s totient function (𝜙(n)) using JavaScript. The Euler’s totient function represents the number of integers less than or equal to a given integer n that are coprime to n. This problem appears very frequently in algorithmic problems related to number theory and can be useful in various coding tests.
What is the Euler’s Totient Function?
The Euler’s totient function 𝜙(n) returns the count of positive integers from 1 to n that are coprime to n. In other words, two numbers a and b are said to be coprime if their greatest common divisor (GCD) is 1.
For example:
- 𝜙(1) = 1 (The only number coprime to 1 is 1 itself)
- 𝜙(2) = 1 (The number less than 2 and coprime to 2 is 1)
- 𝜙(3) = 2 (The numbers less than 3 and coprime to 3 are 1, 2)
- 𝜙(4) = 2 (The numbers less than 4 and coprime to 4 are 1, 3)
- 𝜙(5) = 4 (The numbers less than 5 and coprime to 5 are 1, 2, 3, 4)
Problem Definition
Now, let’s define the coding test problem.
Problem: Write a function to calculate the Euler's totient function for a given integer n. Input: Integer n (1 ≤ n ≤ 106) Output: The value of the Euler's totient function 𝜙(n)
Problem Solving Approach
There are several methods to calculate the Euler’s totient function. The most efficient method is to modify the Sieve of Eratosthenes to compute 𝜙(n) in one go. The time complexity of this method is O(n log log n).
Properties of the Euler’s Totient Function
The key properties required to calculate 𝜙(n) are as follows:
- 𝜙(p) = p – 1, where p is a prime number
- 𝜙(p1 * p2 * … * pk) = p1 * p2 * … * pk * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk)
- 𝜙(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk), where pi are the prime factors of n.
JavaScript Code Implementation
Based on the above properties, let’s write the code to implement the Euler’s totient function.
function eulerPhi(n) {
// Declare and initialize the array
const phi = Array.from({ length: n + 1 }, (_, i) => i);
// Find primes using Sieve of Eratosthenes
for (let p = 2; p <= n; p++) {
if (phi[p] === p) { // If p is prime
for (let k = p; k <= n; k += p) {
// Update the value of 𝜙(k)
phi[k] = Math.floor(phi[k] * (1 - 1 / p));
}
}
}
// Return phi(n) for n
return phi[n];
}
// Test cases
console.log(eulerPhi(1)); // 1
console.log(eulerPhi(2)); // 1
console.log(eulerPhi(3)); // 2
console.log(eulerPhi(4)); // 2
console.log(eulerPhi(5)); // 4
Code Explanation
The code works as follows:
- First, an array phi of size n + 1 is created, and each element is initialized to itself. phi[i] starts with the value of i.
- Loop from 2 to n, checking each number p to see if it is prime. If phi[p] equals p, it is considered prime.
- If p is prime, find its multiples and update the values of phi[k]. The update is performed as 𝜙(k) = 𝜙(k) * (1 - 1/p).
- Finally, return the value of phi[n] to compute the value of the Euler’s totient function for n.
Complexity Analysis
The time complexity of the above code is O(n log log n). This is due to the use of the Sieve of Eratosthenes method. The space complexity is O(n), as it requires space equivalent to the size of n to store the array phi.
Conclusion
We have learned how to implement the Euler's totient function in JavaScript. This method is very useful for algorithm testing and number theory, allowing for efficient computation of the Euler's totient value. Use this code to solve various problems!
Going Further
If you want to practice solving similar problems, working on problems involving the greatest common divisor or least common multiple would also be good practice. Additionally, exploring other concepts in number theory such as primality testing and prime generation is recommended. Enhance your understanding of algorithms through mathematical reasoning!