Codacoda
Back to Academy

math misc

GCD and LCM

The Greatest Common Divisor (GCD) is computed efficiently using the Euclidean algorithm, which repeatedly replaces the larger number with the remainder of division. The Least Common Multiple (LCM) is derived from GCD using the identity LCM(a, b) = |a * b| / GCD(a, b).

Use Cases

  • •Simplifying fractions to lowest terms
  • •Scheduling problems requiring synchronization of periodic events
  • •Cryptographic algorithms such as RSA key generation

Complexity Analysis

MetricBestAverageWorst
TimeO(1)O(log(min(a,b)))O(log(min(a,b)))
SpaceO(1)

Visualization

GCD(48, 18)
Algorithm: a = q × b + r
Speed:1x
Compute GCD(48, 18) using the Euclidean algorithmStep 1 / 6

Implementation

Output

Click "Run Code" to see output...