In this section, I will teach you about two numbers that show up everywhere: the greatest common divisor (GCD) and least common multiple (LCM). You will learn what they mean, how to compute them efficiently, and why so many problems use them.
I will show you the Euclidean algorithm, one of the oldest algorithms in math. It computes GCD fast. You will see why it works and how to use it in your code.
By the end, you will recognize when a problem needs GCD or LCM and solve it in seconds instead of minutes.