C++ Coding Test Course, Finding the Greatest Common Divisor

1. Introduction

One of the common problems that often appears in programming competitions or coding tests is to find the greatest common divisor (GCD) of two numbers.
The greatest common divisor refers to the largest number that divides two natural numbers evenly.
In this article, we will explain an algorithm to calculate the greatest common divisor using C++, and we will delve into the process of solving the problem in detail.

2. Problem Definition

Write a program to find the greatest common divisor of two given natural numbers a and b.
You will receive two natural numbers a, b (1 <= a, b <= 1,000,000) as input, and the output should be the value of the greatest common divisor.

Example Input


48 18

Example Output


6

3. Algorithm Explanation

There are various methods to find the greatest common divisor.
Here, we will explain how to efficiently find the greatest common divisor using the Euclidean algorithm.
The Euclidean algorithm is based on the following principle.

The greatest common divisor GCD(a, b) of two numbers a and b is equal to GCD(b, a mod b).

By repeating this process until b becomes 0, a becomes the greatest common divisor of the two numbers.
That is, GCD(a, 0) = a, so the last remaining number is the greatest common divisor.

Pseudocode for the Euclidean Algorithm

    function GCD(a, b):
        while b ≠ 0:
            temp := b
            b := a mod b
            a := temp
        return a

4. C++ Code Implementation

Based on the algorithm described above, let’s write a program in C++ to calculate the greatest common divisor (GCD).
Below is the source code for the program. 

    #include <iostream>

    using namespace std;

    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    int main() {
        int a, b;
        cout << "Please enter two natural numbers: ";
        cin >> a >> b;

        cout << "Greatest Common Divisor (GCD): " << gcd(a, b) << endl;

        return 0;
    }

5. Code Explanation

The code above works in the following way:

  • Include Header File: By using #include <iostream>, it sets up the use of input/output streams.
  • Define gcd Function: Defines a function that takes two integers a, b as parameters and calculates the greatest common divisor.
  • Main Function: Takes two natural numbers as input from the user, calls the gcd function, and outputs the result.

6. Test Cases

To verify that the above code works correctly, let’s define a few test cases.

Test Case 1

Input


48 18

Output


6

Test Case 2

Input


100 25

Output


25

Test Case 3

Input


13 29

Output


1

7. Time Complexity Analysis

The time complexity of the Euclidean algorithm is O(log(min(a, b))).
This is because the computation time decreases as the sizes of the two numbers shrink.
Thus, this algorithm is one of the efficient methods for calculating the greatest common divisor.

8. Conclusion

In this article, we explored how to find the greatest common divisor using C++.
We examined the process of effectively solving the problem using the Euclidean algorithm.
In algorithm problem-solving, it is essential to have a solid understanding of these basic mathematical concepts and algorithms, so it is recommended to practice and familiarize yourself thoroughly.

9. References