什么是欧几里得算法？

欧几里得算法（Euclidean algorithm），也称为辗转相除法，是一种用于计算两个正整数的最大公约数（GCD）的算法。它是基于以下原理：对于两个正整数a和b（其中a > b），它们的最大公约数等于b和a除以b的余数的最大公约数。通过不断迭代这个过程，直到余数为0，就可以找到最大公约数。

具体的欧几里得算法步骤如下：

1. 将两个正整数a和b进行比较，确保a大于b。

2. 用a除以b，得到商q和余数r。

3. 如果r等于0，则b就是最大公约数。

4. 如果r不等于0，则将b的值赋给a，将r的值赋给b，然后返回第二步继续迭代。

5. 重复执行步骤2到步骤4，直到余数r为0，此时b就是最大公约数。

欧几里得算法是一种简单而有效的算法，常用于计算最大公约数、求解线性同余方程和简化分数等问题。此外，它还可以扩展为扩展欧几里得算法，用于计算最大公约数的同时求解线性方程的整数解。

下面是使用C++编写的演示欧几里得算法的代码示例：

#include <iostream>

// 欧几里得算法
int euclideanAlgorithm(int a, int b) {
    // 确保a大于b
    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }

    int remainder = a % b;
    while (remainder != 0) {
        a = b;
        b = remainder;
        remainder = a % b;
    }

    return b;  // 返回最大公约数
}

int main() {
    int a, b;
    std::cout << "请输入两个正整数：" << std::endl;
    std::cin >> a >> b;

    int gcd = euclideanAlgorithm(a, b);

    std::cout << "最大公约数是：" << gcd << std::endl;

    return 0;
}

在这个示例中，用户会被要求输入两个正整数。然后，euclideanAlgorithm函数使用欧几里得算法计算它们的最大公约数，并返回结果。最后，主函数将打印出计算得到的最大公约数。

请注意，此示例假设用户输入的是有效的正整数。对于实际应用中，你可能需要进行输入验证以确保输入的是合法的正整数。