GCD in python

Python program to find GCD of two numbers

GCD stands for Greatest Common Divisor. GCD of two numbers is the largest positive integer that divides each of the integers.

For example,

Consider the numbers 15 and 25,

Factors of 15 => 5, 3

Factors of 25 => 5, 5

The factors that the two numbers have in common are the gcd of the numbers. The factor 5 is common in both numbers. Hence 5 is the gcd of 15 and 25.

GCD of 15, 25 => 5

Now consider another example,

numbers = 8 and 24

Factors of 8 => 2, 4, 8

Factors of 24 => 2, 4, 6, 8, 12, 24.

The common factors are 2, 4, 8. The greatest of these common factors is 8. So the gcd of 8 and 24 is 8.

Method 1

Procedure :

1. Start.

2. Get the first number as input from the user.

3. Get the second number as input from the user.

4. find the smallest of two numbers and store it in a variable.

5. loop from 0 to small number+1

    => if (n1 % small = 0) and (n2 % small = 0)

        => gcd = i(iterator)

6. print the gcd of two numbers.

7. End. 

Code :

#get the two numbers as input from user

num1 = int(input("Enter first number : "))

num2 = int(input("Enter second number : "))

#find the smallest of two numbers

if(num1>num2):

small = num2

else :

small = num1

for i in range(1, small+1):

#find the number that is divisible by both the numbers

if((num1 % i == 0) and (num2 % i == 0)):

gcd = i

#print the gcd of two numbers

print("GCD = ",gcd)

Method 2

Procedure :

1. Start.

2. Import the math module.

3. Get the first number as input from user.

4. Get the second number as input from the user.

5. Calculate gcd using gcd function in math module.

6. Print the gcd.

7. End.

Code :

#import the math module

import math

#get the two numbers as input from user

num1 = int(input("Enter first number : "))

num2 = int(input("Enter second number : "))

#find the gcd of two numbers using gcd function

gcd = math.gcd(num1, num2)

#print the gcd of two numbers

print("GCD = ", gcd)

Sample input 1 :

54, 24

Sample output 1 :

6

Output screenshot :

Sample input 2 :

20, 10

Sample output 2 :

10

Output screenshot :