In this tutorial, we will learn how to find the Least Common Multiple (LCM) of two numbers in Swift. We’ll understand what LCM is, write an algorithm to compute it, and implement it step by step with a complete Swift program and output.

What is the Least Common Multiple (LCM)?

The Least Common Multiple (LCM) of two integers is the smallest positive integer that is divisible by both numbers. For example, the LCM of 4 and 6 is 12 because 12 is the smallest number divisible by both 4 and 6.

Finding the LCM is useful in problems involving fractions, arithmetic operations, and algebraic equations.

Algorithm to Find LCM

The relationship between the Least Common Multiple (LCM) and Greatest Common Divisor (GCD) is:

LCM(a, b) = (a * b) / GCD(a, b)

Steps of the algorithm:

  1. Find the GCD of the two numbers using the Euclidean algorithm:
    1. Start with two numbers, a and b.
    2. Check if b is 0:
      1. If b is 0, the GCD is a.
      2. If not, proceed to the next step.
    3. Calculate the remainder of dividing a by b, i.e., remainder = a % b.
    4. Replace a with b and b with remainder.
    5. Repeat the process until b becomes 0. At this point, the GCD is the value of a.
  2. Calculate the LCM using the formula (a * b) / GCD(a, b).
  3. Return the computed LCM.
  1. Find the GCD of the two numbers using the Euclidean algorithm.
  2. Calculate the LCM using the formula (a * b) / GCD(a, b).
  3. Return the computed LCM.

This approach is efficient and avoids directly iterating through multiples of the numbers.

Step-by-Step Implementation in Swift

Let’s implement the algorithm step by step in Swift.

1. Define the Function to Compute GCD

We will first write a helper function to compute the GCD of two numbers using the Euclidean algorithm.

</>
Copy
func gcd(_ a: Int, _ b: Int) -> Int {
    var num1 = a
    var num2 = b
    
    while num2 != 0 {
        let remainder = num1 % num2
        num1 = num2
        num2 = remainder
    }
    
    return num1
}

Explanation: This function implements the Euclidean algorithm, which reduces the problem iteratively until the GCD is found. This is a necessary step for computing the LCM.

2. Define the Function to Compute LCM

Using the GCD, we can compute the LCM with the formula (a * b) / GCD(a, b). Here’s the implementation:

</>
Copy
func lcm(_ a: Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

Explanation:

func lcm(_ a: Int, _ b: Int): Defines a function named lcm that accepts two integers a and b.

(a * b): Multiplies the two numbers.

/ gcd(a, b): Divides the product by the GCD of the numbers to compute the LCM.

3. Test the Functions

Let’s test the lcm function with some example inputs:

</>
Copy
// Test cases
let number1 = 4
let number2 = 6
print("The LCM of \(number1) and \(number2) is \(lcm(number1, number2))")

let number3 = 15
let number4 = 20
print("The LCM of \(number3) and \(number4) is \(lcm(number3, number4))")

The function computes the LCM of 4 and 6, as well as 15 and 20.

Complete Swift Program

Here’s the complete program combining the GCD and LCM functions with test cases:

main.swift

</>
Copy
import Foundation

// Function to find the greatest common divisor (GCD)
func gcd(_ a: Int, _ b: Int) -> Int {
    var num1 = a
    var num2 = b
    
    while num2 != 0 {
        let remainder = num1 % num2
        num1 = num2
        num2 = remainder
    }
    
    return num1
}

// Function to find the least common multiple (LCM)
func lcm(_ a: Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

// Test cases
let number1 = 4
let number2 = 6
print("The LCM of \(number1) and \(number2) is \(lcm(number1, number2))")

let number3 = 15
let number4 = 20
print("The LCM of \(number3) and \(number4) is \(lcm(number3, number4))")

Output

</>
Copy
The LCM of 4 and 6 is 12
The LCM of 15 and 20 is 60