GCD and LCM in Python

Euclid's 2,300-year-old algorithm, still the standard GCD.

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

def lcm(a, b):
    return abs(a * b) // gcd(a, b) if a and b else 0

How it works

1. Repeatedly replaces the pair (a, b) with (b, a % b).
2. When the remainder hits zero, a is the GCD.
3. LCM divides the product by the GCD, guarding against zero.

Keywords and builtins used here

• abs
• def
• else
• gcd
• if
• lcm
• return
• while

The run, in numbers

Lines

7

Characters to type

113

Tokens

51

Three-star pace

90 tpm

At the three-star pace of 90 tokens a minute, this run takes about 34 seconds.

Type this snippet

Step 6 of 7 in Flow control, step 21 of 72 in Language basics.

← Previous Next →