From geeksforgeeks.
The Eucliean alogrithm is a way of find the greatest common divisor of two positive integers. GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common prime factors.
36 = 2 * 2 * 3 * 3
60 = 2 * 2 * 3 * 5
GCD = Multiplication of common factors
= 2 * 2 * 3
= 12
Basic Euclidean Algorithm for GCD:
The alogirithm is based on the below facts:
- If we subtract a smaller number from a larger one ( we reduce a large number ), GCD does not change. So, if we keep subtracting repeatedly the larger of two, we end up with GCD.
- Now instead of subtraction, if we divide the larger number, the algorithm stops when we find the reminder 0.
# frozen_string_literal: true
def gcd(first, second)
if first.zero?
return second
end
gcd(second % first, first)
end
first = 36
second = 60
puts "GCD of #{first} and #{second} is #{gcd(first, second)}"