C# Coding Test Course, Implementing Euler Phi Function

One of the common algorithm problems in coding tests is math-related problems. Among them, the Euler’s totient function (φ) is an important topic. In this lecture, we will define the Euler’s totient function and implement an algorithm to solve problems.

What is the Euler’s Totient Function?

The Euler’s totient function counts the number of integers from 1 to n that are coprime to n for a given positive integer n. For example, when n is 5, the numbers coprime to n among 1, 2, 3, 4, 5 are 1, 2, 3, and 4, so φ(5) = 4.

Definition

The Euler’s totient function has the following properties:

φ(1) = 1
For a prime p, φ(p) = p – 1
For two coprime numbers a, b, φ(a*b) = φ(a) * φ(b)

Problem Description

Now, let’s look at an algorithm problem that implements the Euler’s totient function. The problem is to write a program that calculates φ(n) for a given integer n.

Example Problem


    Input: 10
    Output: 4
    Explanation: 1, 3, 7, 9 are coprime to 10.

Problem Solving Process

To solve the problem, I will follow several steps:

Step 1: Understanding the Algorithm

It is fast to use the prime factors of n when calculating φ(n). If n is a prime, then φ(n) = n – 1. The Sieve of Eratosthenes can be used to find primes.

Step 2: Prime Factorization

I will divide n into its prime factors while calculating φ(n). For example, if n is 60:


    Prime factors: 2, 3, 5
    φ(60) = 60 * (1 - 1/2) * (1 - 1/3) * (1 - 1/5) = 16

Step 3: Implementing in C#

Now, let’s implement the algorithm in C#. Below is the code:


    using System;

    class Program
    {
        public static int EulerPhi(int n)
        {
            int result = n; // initial result is n
            for (int i = 2; i * i <= n; i++)
            {
                // Check if i is a prime factor of n
                if (n % i == 0)
                {
                    // Remove prime factors by dividing n
                    while (n % i == 0)
                    {
                        n /= i;
                    }
                    // Multiply the result by (1 - 1/i)
                    result -= result / i;
                }
            }
            // Handle the last prime factor (if n is prime)
            if (n > 1)
            {
                result -= result / n;
            }
            return result;
        }

        static void Main()
        {
            Console.Write("Please enter an integer n: ");
            int n = int.Parse(Console.ReadLine());
            int phi = EulerPhi(n);
            Console.WriteLine($"φ({n}) = {phi}");
        }
    }

Step 4: Testing

I will run the code and test various input values. For example:


    Input: 10
    Output: φ(10) = 4

    Input: 20
    Output: φ(20) = 8

    Input: 1
    Output: φ(1) = 1

Conclusion

In this lecture, we explained the Euler’s totient function and explored how to implement it efficiently in C#. Through the aforementioned processes, I hope you can practice the algorithms and coding skills needed to solve the problem.

Additional Learning Materials

If you want to learn more about the properties of the Euler’s totient function, please refer to the materials below: