Change language

# gcd () in Python

| | |

Naive methods for calculating gcd

1. Using recursion :
2.  ` # Python code to demonstrate naive ` ` # method for calculating gcd (recursion) `   ` def ` ` hcfnaive (a, b): ` ` if ` ` (b ` ` = ` ` = ` ` 0 ` `): ` ` return ` ` a ` ` else ` `: ` ` return ` ` hcfnaive (b, a ` `% ` ` b) ` ` `  ` a ` ` = ` ` 60 ` ` b ` ` = ` ` 48 ` ` `  ` # prints 12 ` ` print ` ` (` ` "The gcd of 60 and 48 is:" ` `, end ` ` = ` ` "") ` ` print ` ` (hcfnaive ( ` ` 60 ` `, ` ` 48 ` `)) `

Output:

` The gcd of 60 and 48 is: 12 `

3. Using

` # Python code to demonstrate naive `
` # method for calculating gcd (Loops) `

` 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 `

` # prints 12 `

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

` print ` ` (computeGCD (` ` 60 ` `, ` ` 48 ` `)) `

Output:

` The gcd of 60 and 48 is: 12 `
4. Using the

` # Python code to demonstrate naive `
` # method for calculating gcd (euclidean algo) `

` def ` ` computeGCD (x, y): `

`   while (y): x , y = y, x % y   return x   a = 60 b = 48    # prints 12 print ( "The gcd of 60 and 48 is:" , end = " ") print (computeGCD ( 60 , 48 )) `

` `

Output:

` The gcd of 60 and 48 is: 12 `
5. Using the Python math.gcd () function

Using gcd () can evaluate the same gcd in just one line.

`  math.gcd (x, y)   Parameters:  x: Non-negative integer whose gcd has to be computed. y: Non-negative integer whose gcd has to be computed.  Return Value:  This method will return an absolute / positive integer value after calculating the GCD of given parameters x and y.  Exceptions:  When Both x and y are 0, function returns 0, If any number is a character, Type error is raised. `

` `

` # Python code for demonstrating gcd () # method for calculating gcd   import math   # prints 12 print ( "The gcd of 60 and 48 is:" , end = "") print (math.gcd ( 60 , 48 )) `

` `

Output:

` The gcd of 60 and 48 is: 12 `

Common exceptions

Some common exceptions in this function:

• Both numbers are 0, gcd is 0
• If only one number is not a number, a type error occurs.

 ` # Python code to demonstrate gcd () ` ` # method exceptions `   ` import ` ` math `   ` # prints 0 ` ` print ` ` (` ` "The gcd of 0 and 0 is: "` `, end ` ` = ` `" ") ` ` print ` ` (math.gcd (` ` 0 ` `, ` ` 0 ` `)) ` ` `  ` # Throws an error ` ` print ` ` (` `" The gcd of a and 13 is: "` `, end ` ` = ` ` "") ` ` print ` ` ( math.gcd (` ` ’a’ ` `, ` ` 13 ` `)) `

Output:

` The gcd of 0 and 0 is: 0 The gcd of a and 13 is: `

Runtime error:

` Traceback (most recent call last) : File "/home/94493cdfb3c8509146254862d12bcc97.py", line 12, in print (math.gcd (’a’, 13)) TypeError:’ str’ object cannot be interpreted as an integer `

This article is provided by Manjeet Singh . If you are as Python.Engineering and would like to contribute, you can also write an article using contribute.python.engineering or by posting an article contribute @ python.engineering. See my article appearing on the Python.Engineering homepage and help other geeks.

## Shop

Learn programming in R: courses

\$

Best Python online courses for 2022

\$

Best laptop for Fortnite

\$

Best laptop for Excel

\$

Best laptop for Solidworks

\$

Best laptop for Roblox

\$

Best computer for crypto mining

\$

Best laptop for Sims 4

\$

Latest questions

NUMPYNUMPY

Common xlabel/ylabel for matplotlib subplots

NUMPYNUMPY

How to specify multiple return types using type-hints

NUMPYNUMPY

Why do I get "Pickle - EOFError: Ran out of input" reading an empty file?

NUMPYNUMPY

Flake8: Ignore specific warning for entire file

NUMPYNUMPY

glob exclude pattern

NUMPYNUMPY

How to avoid HTTP error 429 (Too Many Requests) python

NUMPYNUMPY

Python CSV error: line contains NULL byte

NUMPYNUMPY

csv.Error: iterator should return strings, not bytes

## Wiki

Python | How to copy data from one Excel sheet to another

Common xlabel/ylabel for matplotlib subplots

Check if one list is a subset of another in Python

How to specify multiple return types using type-hints

Printing words vertically in Python

Python Extract words from a given string

Cyclic redundancy check in Python

Finding mean, median, mode in Python without libraries