GCD/LCM (Euclidean Algorithm)

Easy

Algorithm to quickly find GCD and LCM of two numbers

📊 Complexity

Type	Value
Average	O(log min(a, b))
Worst	O(log min(a, b))
Space	O(1)

🏷️ Tags

GCDLCMMathNumber Theory

📖 Introduction

The Euclidean algorithm is over 2000 years old and efficiently finds the Greatest Common Divisor (GCD) of two integers. It uses division remainders iteratively, and once GCD is found, LCM can be easily calculated.

1/15

📘GCD = Greatest Common Divisor

GCD is the largest number that divides both numbers. Example: Let's list divisors of 12 and 18: • Divisors of 12: 1, 2, 3, 4, 6, 12 • Divisors of 18: 1, 2, 3, 6, 9, 18 Common divisors: 1, 2, 3, 6 → The largest? 6! So GCD(12, 18) = 6

GCD/LCM (Euclidean Algorithm)

Easy

GCD/LCM (Euclidean Algorithm)

Algorithm to quickly find GCD and LCM of two numbers

📊 Complexity

Type	Value
Average	O(log min(a, b))
Worst	O(log min(a, b))
Space	O(1)

📘GCD = Greatest Common Divisor