使用C++实现辗转相除法求最大公约数

"欧几里得算法，也称辗转相除法，用于求解整数的最大公约数" 辗转相除法，源于古希腊数学家欧几里得的一项重要发现，是计算两个正整数最大公约数（Greatest Common Divisor, GCD）的经典算法。这个算法基于一个基本原理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。即GCD(a, b) = GCD(b, a % b)。当余数为0时，b即为最大公约数。 在上述C++代码中，我们看到一个名为gcd的函数，它接受两个整数a和b作为参数。函数内部使用了一个while循环，循环条件为b不等于0。在每次循环中，先将b的值临时存储在变量temp中，然后用a除以b的余数更新b的值，最后将a的值更新为temp。这个过程持续进行，直至b等于0，此时a就是最大公约数，函数返回a的值。 在主函数main中，程序首先通过std::cin获取用户输入的两个整数num1和num2。接着调用gcd函数，将num1和num2作为参数传入，计算它们的最大公约数，并将结果存储在变量result中。最后，使用std::cout将计算出的最大公约数输出到屏幕上。 例如，当用户输入15和25时，gcd函数会执行以下步骤： 1. 25除以15，余数为10，更新b为10，a保持为25。 2. 25除以10，余数为5，更新b为5，a保持为10。 3. 10除以5，余数为0，此时b为5，所以5是最大公约数。 因此，程序将输出"GCD of 15 and 25 is 5"。 辗转相除法具有较高的效率，对于大整数尤其如此，其时间复杂度为O(log min(a, b))。由于其简洁的逻辑和高效性，辗转相除法被广泛应用于各种计算领域，包括但不限于数论、密码学以及编程竞赛等。此外，它还启发了更复杂的算法，如扩展欧几里得算法，用于求解最大公约数以及两整数的贝祖等式。