JavaScript Coding Test Course, Euler Pi

Problem Description

Euler’s totient function, or φ(n), is a function that returns the number of integers between 1 and n that are coprime to n. For example, φ(9) = 6 because 1, 2, 4, 5, 7, and 8 are coprime to 9.

The task of this problem is to write a function, calculateTotient, that calculates φ(N) for a given integer N. This function should correctly output the value of φ(n) when n is greater than or equal to 1 and less than or equal to 10^6.

Approach to the Problem

There are several ways to calculate the Euler’s totient, but one of the most efficient methods is to use the prime factorization of n. The Euler’s totient function can be defined as follows:

  • φ(p^k) = p^k – p^(k-1) (where p is a prime number and k is a natural number)
  • φ(n) = n × (1 – 1/p1) × (1 – 1/p2) × … × (1 – 1/pk) (where p1, p2, …, pk are the prime factors of n)

Algorithm Steps

  1. Get the input value N.
  2. Find the prime factors of N.
  3. Apply the φ(n) formula for each prime factor and calculate the result.
  4. Return the result.

Code Implementation

Below is the implementation of the calculateTotient function written in JavaScript. This function returns the Euler’s totient value for the given input n. 

        
function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function calculateTotient(n) {
    let result = n; // Initial value is n
    for (let p = 2; p * p <= n; p++) {
        if (n % p === 0) { // If p is a prime factor of n
            while (n % p === 0) {
                n /= p;
            }
            result *= (p - 1);
            result /= p; // Apply the Euler's totient formula
        }
    }
    if (n > 1) { // If n is prime
        result *= (n - 1);
        result /= n;
    }
    return result;
}

console.log(calculateTotient(9)); // Output: 6

Code Explanation

– The gcd function calculates the greatest common divisor of two numbers. This function is a basic algorithm used for prime factorization.

– In the calculateTotient function, the variable result is initialized to n to account for changes related to the prime factors later.

– Using a for loop, all numbers p from 2 to the square root of n are checked, recognizing p as a prime factor if n is a multiple of p.

– Finally, additional operations are performed when n is greater than 1, specifically if n is prime, to obtain the result.

Conclusion

In this tutorial, we learned how to calculate the Euler’s totient function. I hope you gained an understanding of the importance of using mathematical concepts like prime factorization to solve algorithmic problems. Use topics like this to prepare for JavaScript coding tests.

Additional Learning Resources

– Euler’s Totient Function
– Explanation of Euler’s Totient Function on GeeksforGeeks