33.Euclid’s GCD: The Only Method You Need (Python)

Описание: Learn how to compute the Greatest Common Divisor (GCD) of two numbers using the Euclidean Algorithm in Python. We cover intuition, step-by-step walkthrough, and a clean function you can reuse in interviews and projects.
Examples: GCD(48, 18) = 6, GCD(270, 192) = 6.

def gcd(a, b):
Step 1: Keep looping until the second number becomes zero
(This means we have found the GCD)
while b != 0:
Step 2: Replace (a, b) with (b, a % b)
Example: gcd(48, 18)
a = 48, b = 18 → new (a, b) = (18, 48 % 18) = (18, 12)
a = 18, b = 12 → new (a, b) = (12, 18 % 12) = (12, 6)
a = 12, b = 6 → new (a, b) = (6, 12 % 6) = (6, 0)
Now b = 0, so loop stops
a, b = b, a % b

Step 3: When b becomes 0, the current value of 'a' is the GCD
return a

#Python #CodingInterview #Algorithms #Math #EuclideanAlgorithm