I. In-Class Exercises

Programming Exercises

1. Greatest Common Divisor of M and N: L3071
2. Least Common Multiple of M and N: L3072
3. GCD and LCM Problem: L3073

II. Knowledge Summary

Core Idea

The Euclidean Algorithm, also called the division-based GCD algorithm, is an efficient method for finding the greatest common divisor (GCD) of two positive integers.

Its key principle is:

The GCD of two numbers does not change if the larger number is replaced by the remainder after division.

Algorithm Principle

Steps:

1. Input two positive integers a and b
2. Compute the remainder r = a mod b
3. Replace (a, b) with (b, r)
4. Repeat until r = 0
5. The current divisor is the GCD

1#include<iostream>
2using namespace std;
3
4int gcd(int a, int b) {
5    if (b == 0) {
6        return a;
7    }
8    return gcd(b, a % b);
9}
10
11int main() {
12    int n = 0;
13    int m = 0;
14    while (true) {
15        cin >> n >> m;
16        cout << gcd(n, m) << endl;
17    }
18    return 0;
19}

Execution Example

Find gcd(252, 105):

• 252 % 105 = 42
• 105 % 42 = 21
• 42 % 21 = 0

So the answer is 21.

For gcd(462, 180):

1gcd(462, 180)
2  -> gcd(180, 102)
3  -> gcd(102, 78)
4  -> gcd(78, 24)
5  -> gcd(24, 6)
6  -> gcd(6, 0)
7  -> 6

So gcd(462, 180) = 6.

Algorithm Evaluation

The Euclidean algorithm is very efficient. Its time complexity is about:

O(log(min(a, b)))

That is why it works quickly even for large numbers.

Using GCD to Compute LCM

The formula is:

lcm(a, b) = a / gcd(a, b) * b

Divide first, then multiply, to reduce overflow risk.

Example:

• lcm(462, 180) = 462 / 6 * 180 = 77 * 180 = 13860

Problem-Solving Steps

When a problem asks for GCD or LCM:

1. For two numbers, directly use the Euclidean algorithm
2. For multiple numbers:
   • gcd(a, b, c) = gcd(gcd(a, b), c)
   • lcm(a, b, c) = lcm(lcm(a, b), c)
3. For LCM, compute GCD first, then use the formula
4. No need to force a > b; the algorithm handles that naturally

Common Mistakes

• Writing the wrong recursion base case
• Computing a * b / gcd(a, b) and overflowing before division
• Forgetting edge cases involving zero
• Using repeated subtraction instead of modulo, which is much slower

III. Homework

Programming Exercises

1. GCD of N Numbers: L3074