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.<\/p>\n
Given two integers Here are some examples:<\/p>\n The most famous method for finding the greatest common divisor is the Euclidean algorithm. This method is based on the following principles:<\/p>\n Now we will implement the Euclidean algorithm in Python code. Below is an example of a function that calculates the greatest common divisor:<\/p>\n This function uses a loop to continuously swap the values of the two numbers and calculate the remainder until Let\u2019s write the main code to take input and execute:<\/p>\n 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.<\/p>\na<\/code> and b<\/code>, 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.<\/p>\nInput<\/h3>\n
\n
a<\/code> and b<\/code> (1 \u2264 a<\/code>, b<\/code> \u2264 109<\/sup>).<\/li>\n<\/ul>\nOutput<\/h3>\n
\n
GCD(a, b)<\/code>.<\/li>\n<\/ul>\nExamples<\/h2>\n
\nExample 1:\nInput: 60 48\nOutput: 12\n\nExample 2:\nInput: 101 10\nOutput: 1\n\nExample 3:\nInput: 17 17\nOutput: 17\n<\/pre>\n
Solution Method<\/h2>\n
\n
a<\/code> and b<\/code> is the same as the greatest common divisor of b<\/code> and the remainder of a<\/code> divided by b<\/code>, r<\/code>. That is, GCD(a, b) = GCD(b, r)<\/code>.<\/li>\nr<\/code> becomes 0, and the last remaining b<\/code> will be the greatest common divisor.<\/li>\n<\/ul>\nImplementing the Euclidean Algorithm<\/h2>\n
def gcd(a, b):\n while b != 0:\n a, b = b, a % b\n return a\n<\/code><\/pre>\nb<\/code> becomes 0. The final remaining a<\/code> will be the greatest common divisor.<\/p>\nCode Execution Example<\/h2>\n
if __name__ == \"__main__\":\n a, b = map(int, input(\"Please enter two numbers: \").split())\n result = gcd(a, b)\n print(f\"Greatest Common Divisor: {result}\")\n<\/code><\/pre>\nConclusion<\/h2>\n