C/C++代码实现：数论与图论算法集锦

"C/C++常用代码实现，包括数论算法和图论算法，如最大公约数、最小公倍数、素数判断以及Prim算法求最小生成树等。" 在C/C++编程中，经常会遇到一些基础但重要的算法，这些算法的实现能够提高开发效率。以下是对提供的代码片段的详细解释： 一、数论算法 1. 求两数的最大公约数 (Greatest Common Divisor, GCD) `gcd(a, b)` 函数使用欧几里得算法来计算两个整数 `a` 和 `b` 的最大公约数。如果 `b` 等于0，那么 `gcd` 直接返回 `a`；否则，递归调用 `gcd(b, a mod b)` 直至找到结果。 2. 求两数的最小公倍数 (Least Common Multiple, LCM) `lcm(a, b)` 函数通过不断加 `a` 直到 `lcm` 能够被 `b` 整除来计算最小公倍数。首先确保 `a` 不小于 `b`，然后在循环中检查 `lcm` 是否能被 `b` 整除，如果不能，则 `lcm` 加上 `a` 继续检查。 3. 素数的求法 - A. 小范围判断一个数是否为质数 使用一个简单的遍历方法，从2到数的平方根，如果存在能整除的数，则该数不是质数。 - B. 大范围判断一个数是否为质数，并生成素数表 使用Sieve of Eratosthenes算法，初始化一个数组 `p`，将所有元素标记为真，然后从2开始，每次将所有2的倍数标记为假，直到遍历到50000。最后，保留标记为真的数，即为素数。`getprime` 函数用于生成素数表，`prime` 函数用于查询给定数值是否为素数。 二、图论算法 1. 最小生成树 - Prim算法 `prim(v0)` 函数用于求解给定图的最小生成树。这个算法从一个起始节点 `v0` 开始，维护一个`lowcost`数组记录每个节点到已构造树的最低成本，以及一个`closest`数组记录每个节点最近的已访问节点。初始时，`lowcost` 和 `closest` 都设置为无穷大，除了 `v0` 设置为0。然后，使用一个循环，每次选择与当前树连接且成本最低的未访问节点加入树中，直到所有节点都被包含。 以上是C/C++中常见的数论和图论算法的简单实现，这些代码可以帮助开发者快速处理这些问题，而无需每次都从头编写。在实际项目中，还可以考虑使用更高效的数据结构和优化策略，如优先队列（heap）来改进Prim算法的性能。