GCD of Two Numbers in Python using For loop | Recursion | Function | Euclidean Algorithm

GCD of two numbers in python using for loop, recursion, function, and Euclidean Algorithm.

In this article, you will learn how to find the gcd of two numbers in python using for loop, recursion, function, and Euclidean Algorithm.

 

Example

 

What is GCD of Two Numbers?

 

You should have knowledge of the following topics in Python programming to understand this program:

• Python input() function
• Python while loop
• Python for loop
• Python Functions
• Python Recursion

 

---

GCD of Two Numbers in Python using While loop

1. Create two variables named p & q.
2. Take the two input values and assign these to these variables p & q.
3. Iterate the while loop until p becomes equal to q.
4. Inside the while loop subtract variables p & q from each other until the values of both variables are equal to each other.
5. When while loop completed its iteration then prints the GCD number final output of the program.

 

# GCD of Two Numbers in Python using While loop
p, q = None, None # To store the two positive numbers

print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())

# It will calculate the GCD
while p != q:
	if p > q:
		p -= q
	else:
		q -= p

# It will print the final output
print ("\nGCD =", p)

Run

Output

 

Explanation

In this given program, we have taken two inputs following: 160 & 70 positive integer numbers from the user via the system console. After that, we applied the standard formula to calculate the GCD value of these input numbers.

After the whole calculation, It will return the GCD value 10 the final output of the above program.

 

---

GCD of Two Numbers in Python using For loop

1. Create two variables named p & q.
2. Take the two input values and assign these to these variables p & q.
3. Iterate the for loop from range 1 to p + 1 and checks that p % i & q % i both are remainder is equal to 0, then It will return the GCD number.
4. Print the final output of the program.

 

# GCD of Two Numbers in Python using For loop
p, q = None, None # To store the two positive numbers

print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())

# It will calculate the GCD
for i in range (1, p + 1):
	if i <= q:
		if p % i == 0 and q % i == 0:
			g = i

# It will print the final output
print ("\nGCD =", p)

Run

 

---

GCD of Two Numbers in Python using Recursion

# GCD of Two Numbers in Python using Recursion
# It's the recursive function to find the GCD
def gcd(x, y):
    if x == y:
        return x
    else:
        if x > y:
            x = x - y
        else:
            y = y - x
        return gcd (x, y)

# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())

# It will print the final output
print ("\nGCD =", gcd (p, q))

Run

 

---

GCD of Two Numbers in Python using Function

# GCD of Two Numbers in Python using Function
# It will find the GCD
def gcd(x, y):
    while x != y:
        if x > y:
            x = x - y
        else:
            y = y - x
    return x

# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())

# It will print the final output
print ("\nGCD =", gcd (p, q))

Run

Output

 

---

GCD of Two Numbers in Python using Euclidean Algorithm

Euclidean Algorithm:

• Euclidean Algorithm is a method or procedure for finding the greatest common GCD divisor of two positive integer numbers.
• The largest number of two GCD numbers p & q will divide each other without leaving the remainder.
• Algorithm:
  1. Let x and y be the two input numbers
  2. x modulus y = R --> (x % y)
  3. Let x = y and y = R
  4. Repeat steps 2 & 3 until x mod y is greater than 0
  5. GCD number = y
  6. Finished

 

# GCD of Two Numbers in Python using Euclidean Algorithm
# It's the recursive function to find GCD
def gcd(x, y):
    return y if x == 0 else (x if y == 0 else x if x == y else (gcd(x - y, y) if x > y else gcd(x, y - x)))

# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())

# It will print the final output
print ("\nGCD =", gcd(p, q))

Run

Output