C++ Coding Test Course, Implementing Euler's Phi Function

Understanding mathematics and algorithm problems is very important when preparing for coding tests. Today, we will discuss the Euler’s phi function and how to implement it in C++. The Euler’s phi function returns the number of positive integers less than or equal to a given integer n that are coprime to n. It has many applications in number theory and is useful for solving mathematical problems.

1. Introduction to Euler’s Phi Function

The Euler’s phi function is defined as follows:

For a given n, φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk),

where p1, p2, … pk are all the prime numbers that are coprime to n. For example, φ(6) is calculated as follows:

n = 6, primes p = 2, 3
φ(6) = 6 * (1 – 1/2) * (1 – 1/3) = 6 * 1/2 * 2/3 = 2

1.1 Properties of Euler’s Phi Function

φ(1) = 1
If p is a prime and k is a positive integer, φ(p^k) = p^k * (1 – 1/p)
If two numbers a and b are coprime, φ(ab) = φ(a) * φ(b)

2. Problem Description

Problem: Write a C++ program that calculates the Euler’s phi function for a given integer n.

Input: An integer n (1 ≤ n ≤ 10⁶)

Output: An integer φ(n)

3. Algorithm Design

Calculating the Euler’s phi function directly may be inefficient. We can precompute the primes and then use the formula defined above to calculate φ(n). To do this, we design the algorithm in the following steps.

First, use the Sieve of Eratosthenes to find all primes less than or equal to n.
Use the found primes to calculate φ(n).

3.1 Sieve of Eratosthenes

The Sieve of Eratosthenes is a classical algorithm for quickly finding primes. This algorithm is highly efficient with a time complexity of O(n log log n).

4. C++ Code Implementation

Now, let’s implement the complete algorithm in C++. Below is the C++ code that calculates the Euler’s phi function.

#include <iostream>
#include <vector>

using namespace std;

// Calculate Euler's phi function
int eulerPhi(int n) {
    int result = n; // Initial value is n
    for (int i = 2; i * i <= n; i++) {
        // If i is a divisor of n
        if (n % i == 0) {
            // Adjust the result by multiplying the prime
            while (n % i == 0) {
                n /= i;
            }
            result -= result / i; // Calculate the result
        }
    }
    // If the remaining n is a prime
    if (n > 1) {
        result -= result / n; // Process the result for the prime
    }
    return result;
}

int main() {
    int n;
    cout << "Enter an integer: ";
    cin >> n;
    
    cout << "φ(" << n << ") = " << eulerPhi(n) << endl;
    return 0;
}

5. Code Explanation

The above code works in the following steps:

The eulerPhi(int n) function calculates and returns the Euler’s phi function for the given integer n.
The variable result initially holds the value of n and is updated whenever a prime is found.
If the prime i is a divisor of n, it removes the multiples of i by dividing n by i. During this process, it adjusts the result according to the prime.
After checking all the primes, if n is greater than 1 (i.e., n is prime), it processes it additionally.

6. Code Testing

After completing the code, we can validate the function with various test cases. For example:

When n = 1, φ(1) = 1
When n = 6, φ(6) = 2
When n = 9, φ(9) = 6

7. Performance Analysis

The above algorithm has a time complexity of O(√n) and operates relatively quickly even when n is up to 10⁶. The space complexity is O(1), indicating minimal additional memory usage. For this reason, it can be efficiently used with large datasets.

8. Conclusion

In today’s post, we learned about the concept of Euler’s phi function and how to implement it in C++. The Euler’s phi function can be useful for solving various mathematical problems and plays a significant role in computer programming. Tackling such problems will greatly assist in preparing for coding tests.

If you have any questions or feedback regarding the code, please leave a comment! In the next post, we will cover another algorithm problem. Thank you!

C++ Coding Test Course, Implementing Euler’s Phi Function