Swift Coding Test Course, Finding the Least Common Multiple

Problem Description

When two integers A and B are given, write a program to find the Lowest Common Multiple (LCM) of these two numbers.

Example

  • Input: A = 12, B = 18
  • Output: LCM = 36

Problem Solving Process

1. Definition of Lowest Common Multiple

The lowest common multiple refers to the smallest number among the common multiples of the given two numbers A and B.
The formula to calculate LCM is as follows: 

LCM(A, B) = |A * B| / GCD(A, B)

Here, GCD is the Greatest Common Divisor, which is the largest number among the common divisors of A and B.

2. Algorithmic Approach

To efficiently find the lowest common multiple, first calculate the greatest common divisor, and then apply the above LCM formula.
The Euclidean algorithm is used to find GCD, which is quick and efficient.

Explanation of the Euclidean Algorithm

To find the GCD of two numbers A and B, repeat the following process:

  1. Let the smaller of the two numbers A and B be B, and divide A by B.
  2. Update B to the remainder of A divided by B.
  3. Repeat this process until B becomes 0; then, A is the GCD.

3. Swift Code Implementation

Now, let’s implement code to find the lowest common multiple using the Swift programming language. 

import Foundation

// Find GCD
func gcd(_ a: Int, _ b: Int) -> Int {
    if b == 0 {
        return a
    }
    return gcd(b, a % b)
}

// Find LCM
func lcm(_ a: Int, _ b: Int) -> Int {
    return abs(a * b) / gcd(a, b)
}

// Test example
let A = 12
let B = 18
let result = lcm(A, B)
print("LCM(\(A), \(B)) = \(result)") // LCM(12, 18) = 36

4. Explanation of the Code

– The gcd function takes two integers A and B as parameters and finds the GCD using the Euclidean algorithm.
– The lcm function calculates the lowest common multiple by dividing the product of A and B by the GCD.

5. Additional Tests

Test with several different numbers to ensure the code works well. 


let testCases = [(12, 18), (4, 5), (6, 8), (15, 25)]
for (num1, num2) in testCases {
    let result = lcm(num1, num2)
    print("LCM(\(num1), \(num2)) = \(result)")
}

Conclusion

In this tutorial, we learned how to calculate the Lowest Common Multiple (LCM). We learned to find the GCD using the Euclidean algorithm and then calculate the LCM.
It is important to test the function with various numbers and practice frequently since it is a commonly used mathematical concept.