Example HTML page

A Python program to find the GCD of two numbers.

Greatest Common Divisor (GCD) is also called as Highest Common Factor(HCF) . The GCD of two positive integers is the largest positive integer that divides both the integers. The following are the example programs to find the gcd of two positive integers using math function, if-else statement, for loop and while loop.

Ex: GCD of two positive integers 70 and 18 is 2.

Steps:

1. Factors of 70 = 2 x 5 x 7.

2. Factors of 18 = 2 x 3 x 3

3. From the above two factors of ‘2’ is the common divisor. There the gcd(70,18) is ‘2’.

Finding GCD using math function

import math
print ("The gcd of 70 and 18 is : ",end="") 
print (math.gcd(70,18))

Output

The gcd of 70 and 18 is : 2

Finding GCD using if-else

def gcd(x,y):
    if(y==0):
        return x
    else:
        return gcd(y,x%y)
x=int(input("Enter X: "))
y=int(input("Enter Y: "))
GCD=gcd(x,y)
print("GCD is: ",GCD)

Output

Enter X: 175

Enter Y: 49

GCD is:  7

Explanation

In the above program ‘gcd’ function definition and x and y are the parameters inside it. If y=0 then x is returned. Otherwise x is divided by y and returns y. Then gcd(x,y) ⇒ gcd(175,49) is evaluated and returns 7 as GCD of 175 and 49.

Finding GCD using for loop.

def find_GCD(p, q): 
	if p > q: 
		val = q 
	else: 
		val = p 
	for i in range(1, val+1): 
		if((p % i == 0) and (q % i == 0)): 
			gcd = i 	
	return gcd 
p = 25
q = 7
print ("The gcd of 25 and 7 is : ",end="") 
print (find_GCD(25,7))

Output

The gcd of 25 and 7 is : 1

Finding GCD using while loop

def my_GCD(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 
a = 100
b= 68
print ("The gcd of 100 and 68 is : ",end="") 
print (my_GCD(100,68))

Output

The gcd of 100 and 68 is : 4

 

 

Example HTML page

Leave a Reply

Your email address will not be published. Required fields are marked *

Pin It on Pinterest