Swift Coding Test Course, Euler Pi

This course is designed to prepare for the Swift coding test, where we will deal with the Euler’s totient function. The Euler’s totient function is a crucial concept for understanding the unique properties of integers, frequently appearing in number theory and algorithm problems.

What is the Euler’s Totient Function?

The Euler’s totient function φ(n) represents the count of integers up to n that are coprime with n. Two integers are said to be coprime if they have no common divisors except 1. For example, φ(1) = 1, φ(2) = 1, φ(3) = 2 (1 and 2 are coprime). The Euler’s totient function plays an important role in various problems in cryptography and number theory.

Problem Description

For a given natural number N, write a program that counts the integers from 1 to N that are coprime with n.

Input Format

  • A natural number N (1 ≤ N ≤ 1,000,000) is given on the first line.

Output Format

  • Print a single integer φ(N) on one line.

Sample Input and Output

Input:
10
Output:
4

For the above example, φ(10) is 4. This is because 1, 3, 7, and 9 are coprime with 10.

Problem Solving Approach

To calculate the Euler’s totient function, we can approach it in the following steps:

  1. Understand the concept of prime numbers and find all prime factors of n.
  2. Use φ(n) = n – 1 when n is prime.
  3. Factor n into a product of primes and use the formula to derive φ(n):

    φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

    where p1, p2, …, pk are all the prime factors of n.

Swift Code Implementation

Now, let’s implement the Euler’s totient function in Swift based on the above approach. 

import Foundation

func eulerTotientFunction(_ n: Int) -> Int {
    var result = n
    var number = n
    var p = 2

    while p * p <= number {
        // Check if p is a divisor of number
        if number % p == 0 {
            // Remove all factors of p
            while number % p == 0 {
                number /= p
            }
            // Apply Euler's totient function formula
            result -= result / p
        }
        p += 1
    }

    // If n is prime
    if number > 1 {
        result -= result / number
    }

    return result
}

// Example usage
let n = 10
let result = eulerTotientFunction(n)
print("φ(\(n)) =", result) // Output: φ(10) = 4

Code Explanation

The code above is an example implementation of the Euler’s totient function written in Swift. For a given natural number n, it proceeds as follows:

  • Initialization: Store n in result, store n in number, and initialize p to 2.
  • Finding Divisors: Repeat while p is less than or equal to the square of number. If p is a divisor of number, divide number by p to remove that divisor. Then, divide result by p and store the result back.
  • Checking for Primes: Finally, if number is greater than 1, n is prime, so handle the last prime factor in the φ(n) formula.

Testing

Using the above algorithm, the Euler’s totient function can be calculated quickly and efficiently for various inputs. Below are a few other test cases. 

let testCases = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1000, 10000, 100000, 1000000]
for case in testCases {
    print("φ(\(case)) =", eulerTotientFunction(case))
}

Conclusion

The Euler’s totient function is an important concept in number theory and can be implemented effectively using Swift. Through the above example, we have explained the definition of the Euler’s totient function and the algorithmic approach, hoping it serves as a foundation for tackling more complex problems in the future. Try implementing this function in Swift or other programming languages as practice.

Additional Resources

For more in-depth resources on the Euler’s totient function, see the following: