How do you find the gcd in python?

View Discussion

Improve Article

Save Article

  • Read
  • Discuss
  • View Discussion

    Improve Article

    Save Article

    The Highest Common Factor (HCF), also called gcd, can be computed in python using a single function offered by math module and hence can make tasks easier in many situations.

    Naive Methods to compute gcd

    Way 1: Using Recursion

    Python3

    def hcfnaive(a, b):

        if(b == 0):

            return abs(a)

        else:

            return hcfnaive(b, a % b)

    a = 60

    b = 48

    print("The gcd of 60 and 48 is : ", end="")

    print(hcfnaive(60, 48))

    Output

    The gcd of 60 and 48 is : 12
    

    Way 2: Using Loops 

    Python3

    def computeGCD(x, y):

        if x > y:

            small = y

        else:

            small = x

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

            if((x % i == 0) and (y % i == 0)):

                gcd = i

        return gcd

    a = 60

    b = 48

    print ("The gcd of 60 and 48 is : ", end="")

    print (computeGCD(60,48))

    Output

    The gcd of 60 and 48 is : 12
    

    Way 3: Using Euclidean Algorithm 

    Python3

    def computeGCD(x, y):

       while(y):

           x, y = y, x % y

        return abs(x)

    a = 60

    b = 48

    print ("The gcd of 60 and 48 is : ",end="")

    print (computeGCD(60, 48))

    Output:

    The gcd of 60 and 48 is : 12
    • Both numbers are 0, gcd is 0
    • If only either number is Not a number, Type Error is raised.

    ❮ Math Methods


    Example

    Find the greatest common divisor of the two integers:

    #Import math Library
    import math

    #find the  the greatest common divisor of the two integers
    print (math.gcd(3, 6))
    print (math.gcd(6, 12))
    print (math.gcd(12, 36))
    print (math.gcd(-12, -36))
    print (math.gcd(5, 12))
    print (math.gcd(10, 0))
    print (math.gcd(0, 34))
    print (math.gcd(0, 0))

    Try it Yourself »


    Definition and Usage

    The math.gcd() method returns the greatest common divisor of the two integers int1 and int2.

    GCD is the largest common divisor that divides the numbers without a remainder.

    GCD is also known as the highest common factor (HCF).

    Tip: gcd(0,0) returns 0.


    Syntax

    Parameter Values

    ParameterDescription
    int1 Required. The first integer to find the GCD for
    int2 Required. The second integer to find the GCD for

    Technical Details

    Return Value:An int value, representing the greatest common divisor (GCD) for two integers
    Python Version:3.5

    ❮ Math Methods


    How do you find the GCD of 3 numbers in Python?

    Python code:.
    import math..
    n1=int(input(“ENTER THE FIRST NUMBER “)).
    n2=int(input(“ENTER SECOND NUMBER “)).
    n3=int(input(“ENTER THIRD NUMBER “)).
    print(“THE GCD OF GIVEN NUMBERS:”,math.gcd(math.gcd(n1,n2),n3)).

    How GCD is calculated?

    Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. For example, to compute gcd(48, 180), we find the prime factorizations 48 = 24 · 31 and 180 = 22 · 32 · 51; the GCD is then 2 · 3 · 5 = 22 · 31 · 50 = 12, as shown in the Venn diagram.

    How do you find the GCD of two numbers in a loop in Python?

    Let's create program to find the GCD of two number in python using the loops..
    def GCD_Loop( a, b):.
    if a > b: # define the if condition..
    temp = b..
    temp = a..
    for i in range(1, temp + 1):.
    if (( a % i == 0) and (b % i == 0 )):.
    gcd = i..

    How do you find LCM and GCD in Python?

    Program to Compute LCM Using GCD We require G.C.D. of the numbers to calculate its L.C.M. So, compute_lcm() calls the function compute_gcd() to accomplish this. G.C.D. of two numbers can be calculated efficiently using the Euclidean algorithm. Click here to learn more about methods to calculate G.C.D in Python.