GCD of two number in python

What is GCD?

The Greatest Common Divisor, or GCD, of two numbers is:

• The largest positive integer that divides each of the two numbers without a remainder.
• For example:
  • GCD of 36 and 60 is 12 because 12 is the largest number that can divide both 36 and 60 without a remainder.
• GCD is commonly used in mathematics and programming, such as simplifying fractions, finding least common multiples, and solving problems involving ratios.

There are several ways to compute the GCD of two numbers in Python. Let’s go step-by-step to understand them.

1. Using the math Module

Python’s math.gcd() is a built-in function that calculates the GCD of two numbers efficiently.

import math

# Input two numbers
num1 = 36
num2 = 60

# Calculate GCD
gcd = math.gcd(num1, num2)

print(f"The GCD of {num1} and {num2} is {gcd}")

Output:

The GCD of 36 and 60 is 12

Explanation:

• math.gcd() takes the two arguments ‘num1’, ‘num2’ and yields the GCD.
• Internally, it uses an optimized version of the Euclidean Algorithm.
• This is the fastest and easiest method if you’re working with integers.

2. Using the Euclidean Algorithm (Iterative)

The Euclidean Algorithm is a classic method to find the GCD of two numbers. Here’s how it works step-by-step:

1. Take two numbers a and b.
2. While b is not zero:
   • Compute the remainder of a % b.
   • Replace a with b and b with the remainder.
3. When b becomes 0, the value of a is the GCD.

def gcd_euclidean(a, b):
    while b != 0:
        a, b = b, a % b  # Update a and b
    return a

# Input two numbers
num1 = 36
num2 = 60

# Calculate GCD
gcd = gcd_euclidean(num1, num2)

print(f"The GCD of {num1} and {num2} is {gcd}")

Output:

The GCD of 36 and 60 is 12

Step-by-Step Implementation:

1. Take a = 36, b = 60.
   • Calculate 36 % 60 = 36.
   • Update a = 60, b = 36.
2. Calculate 60 % 36 = 24.
   • Update a = 36, b = 24.
3. Calculate 36 % 24 = 12.
   • Update a = 24, b = 12.
4. Calculate 24 % 12 = 0.
   • Update a = 12, b = 0.
5. Since b = 0, the GCD is 12.

3. Using the Euclidean Algorithm (Recursive)

This is a recursive implementation of the Euclidean Algorithm.

def gcd_recursive(a, b):
    if b == 0:  # Base case: when b is zero
        return a
    return gcd_recursive(b, a % b)  # Recursive step

# Input two numbers
num1 = 36
num2 = 60

# Calculate GCD
gcd = gcd_recursive(num1, num2)

print(f"The GCD of {num1} and {num2} is {gcd}")

Output:

The GCD of 36 and 60 is 12

Step-by-Step Implementation:

• The function gcd_recursive(36, 60) calls gcd_recursive(60, 36).
• The function gcd_recursive(60, 36) calls gcd_recursive(36, 24).
• The function gcd_recursive(36, 24) calls gcd_recursive(24, 12).
• The function gcd_recursive(24, 12) calls gcd_recursive(12, 0).
• The process reaches a dead end when b is 0 and returns 12.

4. Using Brute Force

This method iterates from 1 to the smaller of the two numbers and finds the largest divisor common to both.

def gcd_brute_force(a, b):
    gcd = 1
    for i in range(1, min(a, b) + 1):  # Iterate up to the smaller number
        if a % i == 0 and b % i == 0:  # Check if i divides both numbers
            gcd = i
    return gcd

# Input two numbers
num1 = 36
num2 = 60

# Calculate GCD
gcd = gcd_brute_force(num1, num2)

print(f"The GCD of {num1} and {num2} is {gcd}")

Output:

The GCD of 36 and 60 is 12

Step-by-Step Implementation:

1. Start with gcd = 1.
2. Check all numbers from 1 to min(36, 60) = 36:
   • For i = 12, both 36 % 12 == 0 and 60 % 12 == 0.
   • Update gcd = 12.
3. Complete the loop, and return 12.

Comparison of Methods

Which Method to Use?

• Use math.gcd() for efficiency and ease of use.
• Learn algorithms with Euclidean method either iterative or recursive.
• Try the brute-force method for learning purpose.