1. What is the Euclidean Algorithm?
The Euclidean Algorithm is an efficient method for calculating the greatest common divisor (GCD) of two integers.
This method was first presented as an algorithm by the ancient Greek mathematician Euclid in his book Elements.
The greatest common divisor of two integers a and b has the following properties:
- gcd(a, 0) = a
- gcd(a, b) = gcd(b, a mod b)
Using these two properties, the greatest common divisor can be calculated repeatedly. The time complexity of the Euclidean Algorithm is
O(log(min(a, b))), which is very efficient.
2. Example of the Euclidean Algorithm
Let’s find the greatest common divisor of the two integers 48 and 18.
gcd(48, 18)
1. 48 mod 18 = 12
2. gcd(18, 12)
3. 18 mod 12 = 6
4. gcd(12, 6)
5. 12 mod 6 = 0
6. gcd(6, 0) = 6
Therefore, the greatest common divisor of 48 and 18 is 6.
3. Problem Using the Euclidean Algorithm
Problem: Find the GCD of Two Numbers
For the given two integers a and b, write a function to find their greatest common divisor.
Let’s implement this using Swift.
Problem Constraints
- 0 < a, b < 231
- The return value of the function is the greatest common divisor of the two numbers.
4. Problem Solving Process
To solve the given problem, we will implement it in Swift.
First, we will define the structure of the function to solve this problem.
func gcd(a: Int, b: Int) -> Int {
// Calculate the greatest common divisor when both a and b are 0
if b == 0 {
return a
} else {
// Calculate gcd recursively
return gcd(b, a % b)
}
}
Using the above function, we can find the greatest common divisor of the two numbers a and b. Here, a is one of the two numbers,
b is the other number, and this function is called recursively until b becomes 0.
At the point when b becomes 0, a is returned as the greatest common divisor.
4.1. Example Code
Below is the complete code for finding the greatest common divisor using the Euclidean Algorithm.
func gcd(a: Int, b: Int) -> Int {
if b == 0 {
return a
} else {
return gcd(b, a % b)
}
}
// Example execution
let a = 48
let b = 18
let result = gcd(a: a, b: b)
print("Greatest Common Divisor: \(result)") // Result: Greatest Common Divisor: 6
5. Implementing the Euclidean Algorithm in Swift
The following is an example of implementing the Euclidean Algorithm using a loop in Swift.
Sometimes using a loop can be more efficient in terms of memory usage compared to recursive calls.
func gcdIterative(a: Int, b: Int) -> Int {
var a = a
var b = b
while b != 0 {
let temp = b
b = a % b
a = temp
}
return a
}
// Example execution
let resultIterative = gcdIterative(a: a, b: b)
print("Greatest Common Divisor through Loop: \(resultIterative)") // Result: Greatest Common Divisor through Loop: 6
5.1. Practice with Various Cases
You can practice by applying these functions to various pairs of integers.
For example, try finding the greatest common divisor of 56 and 98, 101 and 103, and so on.
print("gcd(56, 98) = \(gcd(56, 98))") // Result: 14
print("gcd(101, 103) = \(gcd(101, 103))") // Result: 1
6. Conclusion
The Euclidean Algorithm is a simple but very effective algorithm for finding the greatest common divisor.
We have looked at how to implement it in Swift. We were able to learn both methods, iterative and recursive,
and it’s good to consider which method is more efficient depending on the situation.
Such algorithms are often featured in various programming competitions and coding tests, so
it is important to practice thoroughly to become familiar with them.
In addition to the Euclidean Algorithm, I hope you study various algorithms and problem-solving methods to
further enhance your coding skills. Thank you!