Learning C++ Programming from Scratch, Day 400: Finding the Greatest Common Divisor of Two Numbers M and N; Problem Set Answers; Second Method

1088 – Finding the Greatest Common Divisor of Two Numbers M and N

What does this program do?

This program acts like a “numerical relationship analyzer” that can find the greatest common divisor (GCD) between two numbers. For example, for the numbers 12 and 18, their GCD is 6, as 6 is the largest number that can divide both 12 and 18 without leaving a remainder.

How does the program work?

Preparation Phase: The program first prepares the necessary tools (including header files and using namespaces).
Receiving Input: It prompts the user to input two numbers (for example, 12 and 18).
Calculation Process:

Divide the larger number by the smaller number to get the remainder.
If the remainder is 0, then the smaller number is the GCD.
If the remainder is not 0, continue the process using the smaller number and the remainder.

Output Result: Output the calculated GCD.

Why is this method called the “Euclidean algorithm”?

Because it repeatedly uses division and modulus operations, similar to flipping back and forth, until the answer is found. It’s like the “guess the number” game we played as children, narrowing down the range step by step until we find the correct answer.

A simple example

For instance, finding the GCD of 12 and 18:

18 ÷ 12 = 1 remainder 6
12 ÷ 6 = 2 remainder 0 → Since the remainder is 0, 6 is the GCD.

Reference Code

/*1088 - Finding the GCD of two numbers M and N using the Euclidean algorithm*/
#include <bits/stdc++.h>  // Include all common standard library headers
using namespace std;      // Use the standard namespace
// Define two long long variables to store the two user-input numbers
long long m, n;
// Define the recursive function to find the GCD
long long gcd(long long m, long long n) {
    // If the remainder of m divided by n is 0, then n is the GCD
    if (m % n == 0) {
        return n;  // Return n as the result
    } else {
        // Otherwise, recursively call the gcd function with parameters n and m%n
        return gcd(n, m % n);  // This is the "turning" process
    }
}
int main() {
    // Input two positive integers
    cin >> m >> n;
    // Call the gcd function to calculate the GCD and output the result
    cout << gcd(m, n);
    // Program ends normally
    return 0;
}

1. Purpose of the Program

This program uses the Euclidean algorithm to calculate the greatest common divisor (GCD) of two positive integers. The GCD is the largest positive integer that can divide both numbers.

2. Basic Concepts

Greatest Common Divisor (GCD): The largest factor shared by two numbers.
Principle of the Euclidean Algorithm:

Divide the larger number by the smaller number to get the remainder.
If the remainder is 0, the smaller number is the GCD.
If the remainder is not 0, continue the process using the smaller number and the remainder.

Recursion: A method where a function calls itself to solve a problem.

3. Working Principle of the Program

Input Phase

The program waits for the user to input two positive integers.
These two numbers are stored in the variablesm and n.

Calculation Process

Function Call: The main function callsgcd(m, n).
Recursive Calculation:

Calculate the remainder ofm % n;
If the remainder is 0, returnn as the result;
Otherwise, continue calling thegcd function with<code>n and the remainder.

Termination of Recursion: Stop recursion when the remainder is 0.

Output Phase

Directly output the return value of thegcd function.
This value is the GCD of the two numbers.

4. Example Demonstration

Example 1: Input 12 and 18

First call: gcd(18,12)

18 ÷ 12 = 1 remainder 6 → Call gcd(12,6)

Second call: gcd(12,6)

12 ÷ 6 = 2 remainder 0 → Return 6

Result: 6

Example 2: Input 21 and 14

First call: gcd(21,14)

21 ÷ 14 = 1 remainder 7 → Call gcd(14,7)

Second call: gcd(14,7)

14 ÷ 7 = 2 remainder 0 → Return 7

Result: 7

5. Considerations

Input Requirements:

The program assumes that the input is positive integers.
If negative numbers are input, their absolute values should be taken first.
If 0 is input, special handling is required.

Data Types:

Usinglong long type can handle larger integers.
For ordinary-sized numbers,int is sufficient.

Recursion Depth:

The number of recursions in the Euclidean algorithm is not too high.
It will not cause stack overflow even for very large numbers.

Boundary Cases:

When the two numbers are equal, the GCD is the number itself.
When one number is a multiple of the other, the GCD is the smaller number.

6. Learning Value

Through this program, beginners can learn:

The basic syntax of recursive functions.
The mathematical principles of the Euclidean algorithm.
The usage of modulus operation (%).
How to pass function parameters.
Basic input and output operations.
Algorithmic thinking: how to translate mathematical methods into programs.