python coding test course, finding the greatest common divisor

Hello! Today, we will discuss an algorithm problem that finds the “Greatest Common Divisor” in order to help you prepare for coding tests. Accurately calculating the greatest common divisor is essential in many problems, especially those that require both mathematical and algorithmic thinking. In this session, we will use functional programming techniques and practice with the Python language.

Problem Description

Given two integers a and b, please write a program to find the greatest common divisor of these two numbers. The greatest common divisor (GCD) refers to the largest number among the common divisors of the two integers.

Input

  • On the first line, there are two integers a and b (1 ≤ a, b ≤ 109).

Output

  • Print the integer GCD(a, b).

Examples

Here are some examples:

Example 1:
Input: 60 48
Output: 12

Example 2:
Input: 101 10
Output: 1

Example 3:
Input: 17 17
Output: 17

Solution Method

The most famous method for finding the greatest common divisor is the Euclidean algorithm. This method is based on the following principles:

  • The greatest common divisor of two numbers a and b is the same as the greatest common divisor of b and the remainder of a divided by b, r. That is, GCD(a, b) = GCD(b, r).
  • Continue this process until r becomes 0, and the last remaining b will be the greatest common divisor.

Implementing the Euclidean Algorithm

Now we will implement the Euclidean algorithm in Python code. Below is an example of a function that calculates the greatest common divisor:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

This function uses a loop to continuously swap the values of the two numbers and calculate the remainder until b becomes 0. The final remaining a will be the greatest common divisor.

Code Execution Example

Let’s write the main code to take input and execute:

if __name__ == "__main__":
    a, b = map(int, input("Please enter two numbers: ").split())
    result = gcd(a, b)
    print(f"Greatest Common Divisor: {result}")

Conclusion

In this article, we learned the principle of the Euclidean algorithm through the problem of finding the greatest common divisor and actually implemented it in Python. This problem has various applications and the same principles can be applied when solving other algorithm problems. I hope you experience the harmony of mathematics and programming while solving algorithmic challenges.

One thing I want to emphasize as we conclude!

The foundation of preparing for coding tests is to solve a wide variety of problems. By solving many problems and reviewing the process, you can significantly improve your coding skills. Thank you!