\n 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.
\n The greatest common divisor refers to the largest number that divides two natural numbers evenly.
\n 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.\n <\/p>\n
\n Write a program to find the greatest common divisor of two given natural numbers a and b.
\n 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.\n <\/p>\n
\n There are various methods to find the greatest common divisor. \n The greatest common divisor GCD(a, b) of two numbers a and b is equal to GCD(b, a mod b).\n <\/p><\/blockquote>\n \n By repeating this process until b becomes 0, a becomes the greatest common divisor of the two numbers. \n Based on the algorithm described above, let\u2019s write a program in C++ to calculate the greatest common divisor (GCD). \n The code above works in the following way:\n <\/p>\n \n To verify that the above code works correctly, let’s define a few test cases.\n <\/p>\n \n The time complexity of the Euclidean algorithm is O(log(min(a, b))). \n In this article, we explored how to find the greatest common divisor using C++.
\n 48 18
\n <\/code><\/p>\nExample Output<\/h3>\n
\n 6
\n <\/code><\/p>\n3. Algorithm Explanation<\/h2>\n
\n Here, we will explain how to efficiently find the greatest common divisor using the Euclidean algorithm.
\n The Euclidean algorithm is based on the following principle.\n <\/p>\n
\n That is, GCD(a, 0) = a, so the last remaining number is the greatest common divisor.\n <\/p>\nPseudocode for the Euclidean Algorithm<\/h3>\n
\n function GCD(a, b):\n while b \u2260 0:\n temp := b\n b := a mod b\n a := temp\n return a\n <\/pre>\n
4. C++ Code Implementation<\/h2>\n
\n Below is the source code for the program.\n <\/p>\n\n #include <iostream>\n\n using namespace std;\n\n int gcd(int a, int b) {\n while (b != 0) {\n int temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n }\n\n int main() {\n int a, b;\n cout << \"Please enter two natural numbers: \";\n cin >> a >> b;\n\n cout << \"Greatest Common Divisor (GCD): \" << gcd(a, b) << endl;\n\n return 0;\n }\n <\/pre>\n5. Code Explanation<\/h2>\n
\n
#include <iostream><\/code>, it sets up the use of input\/output streams.<\/li>\ngcd<\/code> function, and outputs the result.<\/li>\n<\/ul>\n6. Test Cases<\/h2>\n
Test Case 1<\/h3>\n
Input<\/h4>\n
\n 48 18
\n <\/code><\/p>\nOutput<\/h4>\n
\n 6
\n <\/code><\/p>\nTest Case 2<\/h3>\n
Input<\/h4>\n
\n 100 25
\n <\/code><\/p>\nOutput<\/h4>\n
\n 25
\n <\/code><\/p>\nTest Case 3<\/h3>\n
Input<\/h4>\n
\n 13 29
\n <\/code><\/p>\nOutput<\/h4>\n
\n 1
\n <\/code><\/p>\n7. Time Complexity Analysis<\/h2>\n
\n This is because the computation time decreases as the sizes of the two numbers shrink.
\n Thus, this algorithm is one of the efficient methods for calculating the greatest common divisor.\n <\/p>\n8. Conclusion<\/h2>\n
\n We examined the process of effectively solving the problem using the Euclidean algorithm.
\n 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.\n <\/p>\n9. References<\/h2>\n