C++ Coding Test Course, Euler's Pi

Hello! In this tutorial, we will learn how to solve the Euler’s Totient Function problem using C++. This problem involves finding the count of integers that are coprime to a given integer n, which are less than or equal to n.

What is the Euler’s Totient Function?

The Euler’s Totient Function φ(n) is a function that represents the count of integers that are coprime to the number n. For example:

φ(1) = 1 (1 is always coprime with itself)
φ(2) = 1 (The only number less than 2 that is coprime with 2 is 1)
φ(3) = 2 (1 and 2 are coprime with 3)
φ(4) = 2 (1 and 3 are coprime with 4)
φ(5) = 4 (1, 2, 3, 4 are coprime with 5)

Problem Description

Write an algorithm to calculate the value of φ(n) for a given n. The input will be an integer n (1 ≤ n ≤ 10⁶).

Example Input

Example Output

Explanation: 1, 3, 7, and 9 are coprime with 10.

Steps to Solve the Problem

Step 1: Understand the Properties

The value of the Euler’s Totient Function has the following properties:

If p is a prime number, then φ(p) = p – 1
If p is a prime number, then φ(p^k) = p^k – p^k-1 = p^k(1 – 1/p)
If two primes p and q are coprime, then φ(p*q) = φ(p) * φ(q)

Step 2: Use the Sieve of Eratosthenes for Range Calculation

To find the Euler’s Totient values for all numbers up to n, we can utilize the Sieve of Eratosthenes method to find composite numbers and calculate the totient values. This method operates with a time complexity of O(n log log n).

Step 3: Implement the Algorithm

Here is an implementation in C++ for calculating the Euler’s Totient Function:


#include <iostream>
#include <vector>

using namespace std;

void eulerTotient(int n, vector<int>& phi) {
    for (int i = 0; i <= n; i++) {
        phi[i] = i; // initialize phi
    }
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) { // if i is prime
            for (int j = i; j <= n; j += i) {
                phi[j] *= (i - 1); // multiply by (1 - 1/p) since prime p is included
                phi[j] /= i;
            }
        }
    }
}

int main() {
    int n;
    cout << "Please enter the value of n: ";
    cin >> n;

    vector<int> phi(n + 1);
    eulerTotient(n, phi);

    cout << "φ(" << n << ") = " << phi[n] << endl;
    return 0;
}

Step 4: Explanation of the Code

In the above code:

First, we initialize φ[i] for each number.
Next, we find the prime i and update φ[j] for all multiples j.
Finally, the Euler’s Totient value for n is stored in φ[n].

Step 5: Performance Improvement

This algorithm has a performance of O(n log log n), which works efficiently even for the maximum range of 10⁶.

Conclusion

In this tutorial, we covered how to efficiently calculate the Euler’s Totient Function using C++. The method utilizing the Sieve of Eratosthenes is fast and useful, and it can also be beneficial for coding tests. Keep studying various algorithms to enhance your coding skills!

C++ Coding Test Course, Euler’s Pi