Skip to content

Instantly share code, notes, and snippets.

@dylanchapell
Created November 1, 2022 18:13
Show Gist options
  • Save dylanchapell/ef1aa0fe8d7223901004381cbe159445 to your computer and use it in GitHub Desktop.
Save dylanchapell/ef1aa0fe8d7223901004381cbe159445 to your computer and use it in GitHub Desktop.
Quick python program to calculate the greatest common divisor of two numbers using the euclidian algorithm and print out steps
import math
print("We will compute gcd(a,b)")
firstA = int(input("Enter A: "))
firstB = int(input("Enter B: "))
A = firstA
B = firstB
lastR = 1
R = 1
while R != 0:
lastR = R
Q = math.trunc(A/B)
R = A - B*Q
print(str(A)+"="+str(B)+"*"+str(Q)+"+"+str(R))
A = B
B = R
print("gcd("+str(firstA)+","+str(firstB)+") = "+str(lastR))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment