Ruby - Find the Greatest Common Divisor (GCD)

1. Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest number that can exactly divide both numbers without leaving a remainder. It is a fundamental concept in number theory and plays a pivotal role in various fields like cryptography and coding theory. In this tutorial, we will outline a Ruby program that calculates the GCD of two given numbers using the Euclidean algorithm.

2. Program Steps

1. Initialize the Ruby development environment.

2. Ask the user to provide two numbers.

3. Use the Euclidean algorithm to compute the GCD of the given numbers.

4. Display the GCD result to the user.

3. Code Program

# Prompting the user for two numbers
puts "Enter the first number:"
num1 = gets.chomp.to_i
puts "Enter the second number:"
num2 = gets.chomp.to_i
# Define a method to compute the GCD using the Euclidean algorithm
def gcd(a, b)
  while b != 0
    a, b = b, a % b
  end
  a
end
# Compute the GCD of the provided numbers
result = gcd(num1, num2)
# Display the result
puts "The GCD of #{num1} and #{num2} is: #{result}"

Output:

Enter the first number:
56
Enter the second number:
98
The GCD of 56 and 98 is: 14

Explanation:

1. gets: Captures user input. By default, it collects the input as a string.

2. chomp: Used to remove the newline character that's appended when the user presses Enter.

3. to_i: Transforms the input string to an integer.

4. gcd: This is a custom method that employs the Euclidean algorithm. In the algorithm, the GCD of two numbers also divides their difference. So, to compute the GCD of two numbers a and b, we replace the larger number with the absolute difference of the numbers, and repeat the process until b becomes zero.

5. a, b = b, a % b: This is a neat Ruby trick for simultaneously assigning values. Here, b takes the value of a % b (the remainder of a divided by b), and a takes the prior value of b.