C++应用密码学任务:最大公约数

在C++中，计算两个整数的最大公约数（Greatest Common Divisor, GCD）通常可以使用欧几里得算法（Euclidean Algorithm），也称为辗转相除法。这个算法的基本思想是：两个整数a和b（假设a > b），它们的最大公约数等于b和a除以b的余数c的最大公约数。如果余数为0，则b就是最大公约数；否则继续用a替换b，用c替换a，直到余数为0。

以下是使用递归方式实现欧几里得算法的一个简单示例：

#include <iostream>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main() {
    int num1, num2;
    std::cout << "请输入两个整数: ";
    std::cin >> num1 >> num2;
    std::cout << "这两个数的最大公约数是: " << gcd(num1, num2);
    return 0;
}

在这个程序中，`gcd()`函数会一直递归调用自身，直到找到最大公约数。当输入的第二个数字为零时，算法停止，返回第一个数字作为结果。