GCD & LCM
Greatest Common Divisor and Least Common Multiple using the Euclidean Algorithm.
Ready to calculate GCD & LCM.
Intuition
If a number divides both A and B, it must also divide their difference (A - B). By extension, it divides the remainder of A % B. We can keep reducing the problem until the remainder is 0.
Concept
- GCD (Greatest Common Divisor): The largest number that divides both A and B without leaving a remainder.
- LCM (Least Common Multiple): The smallest number that is a multiple of both A and B.
- Relation:
LCM(A, B) = (A * B) / GCD(A, B)
How it Works
Euclidean Algorithm:
- Calculate remainder
R = A % B. - If
R == 0, thenBis the GCD. - Otherwise, set
A = BandB = R, and repeat.
Step-by-Step Breakdown
Watch the visualization:
- See how the numbers shrink rapidly.
- The process stops when the remainder becomes 0.
- The last non-zero divisor is the GCD.
When to Use
- Simplifying fractions.
- Scheduling problems (LCM).
- Cryptography (RSA algorithm).
When NOT to Use
- When numbers are extremely large (though it's still very efficient, O(log(min(A, B)))).
How to Identify
"Common divisor", "Simultaneous events (LCM)", "Simplify ratio".
Frequently Asked Questions
What is GCD & LCM?
Greatest Common Divisor and Least Common Multiple using the Euclidean Algorithm.
What is the time complexity of GCD & LCM?
The time complexity is: Best case varies, Average case O(log(min(A, B))), Worst case varies. Space complexity is varies.