Swift Program to Find the Greatest Common Divisor (GCD)

In this tutorial, we will learn how to find the greatest common divisor (GCD) of two numbers in Swift. We will understand what GCD is, write the algorithm to compute it, and implement it step by step with a final Swift program and output.

What is the Greatest Common Divisor (GCD)?

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 54 and 24 is 6 because 6 is the largest number that divides both 54 and 24.

Finding the GCD is a fundamental problem in mathematics and computer science, and it is often used in problems involving fractions, modular arithmetic, and number theory.

Algorithm to Find GCD

One of the most efficient ways to find the GCD is by using the Euclidean algorithm, which is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Steps of the algorithm:

  1. Take two numbers, a and b.
  2. Check if b is 0. If yes, the GCD is a.
  3. If not, compute a % b (remainder of dividing a by b).
  4. Replace a with b and b with a % b.
  5. Repeat until b becomes 0.

This process ensures that we efficiently reduce the problem size in each iteration until the GCD is found.

Step-by-Step Implementation in Swift

Let’s translate the algorithm into Swift code step by step.

1. Define the Function

First, define a function gcd that takes two integers as parameters. Inside the function, implement the steps of 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:

  1. func gcd(_ a: Int, _ b: Int): Defines a function named gcd that accepts two integers a and b.
  2. var num1 = a, var num2 = b: Create mutable copies of the inputs for processing.
  3. while num2 != 0: The loop continues until the second number becomes 0.
  4. let remainder = num1 % num2: Calculate the remainder when num1 is divided by num2.
  5. num1 = num2, num2 = remainder: Update num1 and num2 for the next iteration.
  6. return num1: When the loop exits, num1 holds the GCD.

2. Test the Function

Now that the function is ready, let’s test it with some example inputs to ensure it works as expected.

</>
Copy
// Test cases
let number1 = 54
let number2 = 24
print("The GCD of \(number1) and \(number2) is \(gcd(number1, number2))")

let number3 = 81
let number4 = 153
print("The GCD of \(number3) and \(number4) is \(gcd(number3, number4))")

In this test case, the function computes the GCD of 54 and 24, as well as 81 and 153.

Complete Swift Program

Here’s the complete program with both the function and test cases:

</>
Copy
import Foundation

// Function to find the greatest common divisor
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
}

// Test cases
let number1 = 54
let number2 = 24
print("The GCD of \(number1) and \(number2) is \(gcd(number1, number2))")

let number3 = 81
let number4 = 153
print("The GCD of \(number3) and \(number4) is \(gcd(number3, number4))")

Output

The GCD of 54 and 24 is 6
The GCD of 81 and 153 is 9