दो Numbers का GCD Python में — code, output और dry run

Problem statement

Approach 1: simple loop

Search downwards from the smaller number: the first value that divides both numbers exactly is the GCD. Simple, and it shows what "common divisor" means.

a, b = 48, 18

gcd = 1
for i in range(min(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        gcd = i
        break

print(gcd)
# Output: 6

The loop starts at min(a, b) because no divisor of both can exceed the smaller number, and it stops at the first hit — the greatest one.

Approach 2: reusable function

Euclid's algorithm is the classic: repeatedly replace the pair (a, b) with (b, a % b) until b becomes 0; the remaining a is the GCD. Dramatically faster than searching.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(48, 18))   # 6
print(gcd(100, 75))   # 25
print(gcd(17, 5))     # 1 — coprime

Each step shrinks the numbers fast — the remainder is always smaller than the divisor — so even huge pairs finish in a handful of iterations.

Approach 3: Pythonic alternative

The standard library ships the algorithm: math.gcd(). There is also math.lcm() next to it for the partner concept.

import math

print(math.gcd(48, 18))          # 6
print(math.gcd(48, 18, 24))      # 6 — takes any number of arguments

Know Euclid's version by hand for exams; trust this one in real code.

Dry run

Common errors

• दोनों variables साथ update न करना — a, b = b, a % b tuple assignment ही सही है।
• Remainder step भूलना — loop कभी खत्म नहीं होगा।
• 1 से ऊपर की ओर search करना — common divisor तो मिलेगा, पर greatest नहीं।
• GCD और LCM mix करना — LCM(4,6)=12, GCD(4,6)=2।
• Zero का case — gcd(n, 0) = n होता है, Euclid यह अपने आप संभाल लेता है।

Practice on PyDebug

Concept समझने के बाद इन free problems को browser में solve करें:

• Range boundary practice
• Operator precedence practice
• Variables and assignment practice