TypeScript: Find the GCD of Two Numbers

1. Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. In this post, we will implement a TypeScript program to find the GCD of two numbers using the Euclidean algorithm.

2. Program Overview

The Euclidean algorithm, which is the basis for our program, finds the GCD of two numbers by repeatedly taking the remainder of the division of the two numbers until one of them becomes 0. The non-zero remainder then becomes the GCD.

3. Code Program

function gcd(a: number, b: number): number {
    // If one of the numbers is 0, the other number is the GCD
    if (b === 0) return a;

    // Otherwise, recursively compute the GCD
    return gcd(b, a % b);
}

// Test the function
const num1 = 56;
const num2 = 98;
const result = gcd(num1, num2);
console.log(`The GCD of ${num1} and ${num2} is:`, result);

Output:

The GCD of 56 and 98 is: 14

4. Step By Step Explanation

1. We declare a gcd function that accepts two numbers a and b.

2. Inside the function, we check if b is equal to 0. If it is, then a is the GCD.

3. If not, we recursively call the gcd function, passing in b and the remainder of the division of a by b (a % b).

4. This process continues, reducing the size of the numbers with each recursive call, until b becomes 0.

5. At this point, the function returns a as the GCD.

6. We then test the function using two numbers, 56 and 98 and display the result.