GCD

Github logo Edit on GitHub

The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

gcd(m,n)=gcd(n,m%n)

Base case:
gcd(m,0)=m

Program:

n1=int(input("Enter a Number"))
n2=int(input("Enter another Number"))
while n2!=0:
  rem=n1%n2
  n1=n2
  n2=rem
print ("GCD of given numbers is:",n1)
Input:
Enter a Number 54
Enter another Number 45
Output:
GCD of given numbers is: 9
Previous
Square Root Program
Next
Exponentiation

References

  • Allen B. Downey, “Think Python: How to Think Like a Computer Scientist‘‘, 2nd edition, Updated for Python 3, Shroff/O‘Reilly Publishers, 2016 (http://greenteapress.com/wp/thinkpython/)
  • Guido van Rossum and Fred L. Drake Jr, ―An Introduction to Python – Revised and updated for Python 3.2, Network Theory Ltd., 2011.
  • John V Guttag, ―Introduction to Computation and Programming Using Python‘‘, Revised and expanded Edition, MIT Press , 2013
  • Robert Sedgewick, Kevin Wayne, Robert Dondero, ―Introduction to Programming in Python: An Inter-disciplinary Approach, Pearson India Education Services Pvt. Ltd., 2016.
  • Timothy A. Budd, ―Exploring Python‖, Mc-Graw Hill Education (India) Private Ltd.,, 2015. 4. Kenneth A. Lambert, ―Fundamentals of Python: First Programs‖, CENGAGE Learning, 2012.
  • Charles Dierbach, ―Introduction to Computer Science using Python: A Computational Problem-Solving Focus, Wiley India Edition, 2013.
  • Paul Gries, Jennifer Campbell and Jason Montojo, ―Practical Programming: An Introduction to Computer Science using Python 3‖, Second edition, Pragmatic Programmers, LLC, 2013.