Swift Coding Test Course, Implementing the Euler's Phi Function

Introduction

Algorithm problem solving is fundamental to programming and plays an important role in coding interviews. In this course, we will implement Euler’s Totient Function in Swift. The Euler’s Totient Function returns the count of integers that are coprime to a given positive integer n, i.e., it counts the integers from 1 to n that have a greatest common divisor of 1 with n.

Algorithm Problem Description

Problem: Given an integer n (1 ≤ n ≤ 10⁶), calculate and return the Euler’s Totient Function.

For example, when n is 6, the integers that are coprime to 1, 2, 3, 4, 5, 6 are 1 and 5, and the integers that are coprime to 2 are 1, 3, and 5, resulting in a final count of 2. Therefore, φ(6) = 2.

Approach to the Problem

The Euler’s Totient Function can be calculated efficiently by utilizing the prime factors of the given number. This function can be derived using the following properties:

φ(p) = p – 1 (p is prime)
φ(p^k) = p^k – p^k-1 (p is prime, k is a positive integer)
φ(mn) = φ(m) * φ(n) (m and n are coprime)

Therefore, the Euler’s Totient Function can be calculated through prime factorization. We will proceed with the following steps to solve the problem:

Receive an integer n from the user.
Find the prime factors of n and use them to calculate the Euler’s Totient Function.
Print the result of the calculation.

Swift Code Implementation

Now, let’s implement the Euler’s Totient Function using Swift. The code is as follows:

Euler’s Totient Function in Swift

func eulerTotient(n: Int) -> Int { var result = n var i = 2


            while i * i <= n {
                if n % i == 0 {
                    while n % i == 0 {
                        n /= i
                    }
                    result -= result / i
                }
                i += 1
            }
            
            if n > 1 {

                result -= result / n

            }
            return result

        }

// Example usage let n = 6 print("φ(\(n)) = \(eulerTotient(n: n))") // Output: φ(6) = 2

Code Explanation

The above code defines a method for calculating the Euler’s Totient Function. Each step is as follows:

Initialization: The input value n is stored in the result variable, which will hold the final result.
Prime Factorization: Starting from 2, we increment i to find the prime factors of n, proceeding until i squared is less than or equal to n.
Condition Check: If n is divisible by i, we divide n by i using a while loop. This process repeats as long as n can be divided by i.
Result Update: The result variable is updated for the current prime factor i, based on the properties of the phi function.
Remaining Prime Factor Handling: After the loop, if n is greater than 1 (indicating a prime factor has been found), we update the result accordingly.

Complexity Analysis

The time complexity of this algorithm is O(√n). This is due to the double-loop structure required to find the prime factors of n. In the worst case, prime factors must be checked up to the square root of n, and since n is continually divided, it results in a very efficient algorithm overall.

Conclusion

In this course, we implemented the Euler’s Totient Function to calculate the number of coprime integers. This problem is a common topic in various algorithm examinations and can be solved efficiently using prime factorization. By implementing it in Swift, we hope to enhance programming skills and deepen the understanding of algorithms.

Swift Coding Test Course, Implementing the Euler’s Phi Function