C/C++算法大全：数论与图论基础

算法大全是针对C和C++编程语言编写的实用资源，主要涵盖了数论算法和图论算法两个核心部分。以下是各部分的详细解读： 1. **数论算法** - **最大公约数**：`gcd(a, b)` 函数通过欧几里得算法计算两个整数 `a` 和 `b` 的最大公约数。该算法递归地将问题简化为较小的子问题，直到找到 `b` 为0时，最大公约数即为 `a`。 - **最小公倍数**：`lcm(a, b)` 函数利用辗转相除法（也称欧几里得算法）的逆运算，先确保 `a` 大于 `b`，然后从 `a` 开始，每次加 `a` 直到能被 `b` 整除，此时 `lcm` 就是结果。 - **素数判断**： - A. 小范围质数检测：`prime(n)` 函数通过试除法检查 `n` 是否为质数，只测试到其平方根即可，如果存在因子，则返回 `false`，否则为 `true`。 - B. 长整数范围质数查找与素数表生成：`getprime` 函数首先初始化一个布尔数组 `p`，标记1到50000之间的数是否为素数。接着通过循环，对于每个素数 `i`，将 `i` 的所有倍数标记为合数，最后输出小于或等于50000的素数列表。 2. **图论算法** - **最小生成树**： - **Prim算法**：`prim(v0)` 函数实现了Prim算法，用于在图中找到连接所有顶点的最小生成树。它维护了两个数组 `lowcost` 和 `closest`，分别记录当前已选择边的最低成本和最近的未连接顶点，通过迭代过程不断添加边，直到形成一棵树。 这个资源提供了实用的数论和图论基础算法实现，对于学习C/C++编程和理解这些算法的工作原理非常有帮助，特别是对于需要解决实际问题中的优化和效率问题的开发者来说，这些函数可以直接应用于项目中。同时，对素数的处理也为密码学、数据加密等领域提供了基础工具。