YouTip

## C Exercise Example 16: Greatest Common Divisor (GCD) and Least Common Multiple (LCM) In this tutorial, we will explore how to calculate the **Greatest Common Divisor (GCD)** and the **Least Common Multiple (LCM)** of two positive integers using the C programming language. This is a classic algorithmic problem that demonstrates the practical application of number theory in computer science. --- ### Problem Description Write a C program that takes two positive integers, $m$ and $n$, as input from the user, and calculates their: 1. **Greatest Common Divisor (GCD)** (also known as the Greatest Common Factor) 2. **Least Common Multiple (LCM)** --- ### Mathematical Analysis & Algorithm To solve this problem efficiently, we can break it down into two parts: #### 1. Finding the Least Common Multiple (LCM) There is a fundamental mathematical relationship between the product of two numbers, their GCD, and their LCM: $$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$$ Therefore, the key to solving this problem lies in efficiently finding the GCD first. #### 2. Finding the Greatest Common Divisor (GCD) using the Euclidean Algorithm The most efficient way to find the GCD of two integers is the **Euclidean Algorithm** (also known as the division-by-remainder method). ##### Mathematical Proof: Let $c$ be the greatest common divisor of $a$ and $b$, denoted as $c = \text{gcd}(a, b)$, where $a \ge b$. Let $r$ be the remainder of $a$ divided by $b$: $$r = a \pmod b$$ We can express $a$ and $b$ as multiples of $c$: $$a = k \cdot c, \quad b = j \cdot c$$ *(where $k$ and $j$ are coprime; otherwise, $c$ would not be the greatest common divisor).* From the division algorithm, we can write: $$r = a - m \cdot b = k \cdot c - m \cdot j \cdot c = (k - m \cdot j) \cdot c$$ This shows that the remainder $r$ is also a multiple of $c$. Furthermore, $(k - m \cdot j)$ and $j$ are coprime. Thus, the greatest common divisor of $b$ and $r$ is also $c$. This proves the recurrence relation: $$\text{gcd}(a, b) = \text{gcd}(b, a \pmod b)$$ ##### Step-by-Step Algorithm: 1. **Divide $a$ by $b$** to find the remainder $r$ ($0 \le r < b$). 2. **Check the remainder**: If $r = 0$, the algorithm terminates, and $b$ is the GCD. 3. **Swap and Repeat**: If $r \neq 0$, set $a \leftarrow b$ and $b \leftarrow r$, then return to Step 1. --- ### C Source Code Implementation Below is the complete, standard C program implementing the Euclidean algorithm. ```c #include int main() { int a, b, temp, remainder, original_product; printf("Please enter two positive integers:\n"); // Read two integers from user input scanf("%d %d", &a, &b); // Ensure 'a' is greater than or equal to 'b' if (a < b) { temp = b; b = a; a = temp; } // Store the product of the original numbers to calculate LCM later original_product = a * b; // Calculate the initial remainder remainder = a % b; // Loop until the remainder becomes 0 while (remainder != 0) { a = b; // Replace 'a' with 'b' b = remainder; // Replace 'b' with the remainder remainder = a % b; // Calculate the new remainder } // When the loop terminates, 'b' holds the GCD int gcd = b; int lcm = original_product / gcd; printf("The Greatest Common Divisor (GCD) is: %d\n", gcd); printf("The Least Common Multiple (LCM) is: %d\n", lcm); return 0; } ``` --- ### Sample Output #### Test Case 1: ```text Please enter two positive integers: 12 26 The Greatest Common Divisor (GCD) is: 2 The Least Common Multiple (LCM) is: 156 ``` #### Test Case 2: ```text Please enter two positive integers: 15 25 The Greatest Common Divisor (GCD) is: 5 The Least Common Multiple (LCM) is: 75 ``` --- ### Considerations & Best Practices 1. **Integer Overflow**: In the statement `original_product = a * b;`, if the two input numbers are very large, their product might exceed the maximum limit of a standard 32-bit signed `int` (which is $2,147,483,647$). To prevent integer overflow, you can: * Use `long long` instead of `int` for storing the product and calculating the LCM. * Alternatively, calculate the LCM by dividing first to keep intermediate values smaller: $$\text{LCM} = (a / \text{GCD}) \times b$$ 2. **Input Validation**: The Euclidean algorithm assumes positive integers. In production environments, always validate that the user inputs are greater than zero before running the calculation.