C++算法实例：最大公约数与最小公倍数及素数判断

本文档主要介绍了几个基本的C++算法实例，包括数论算法和图论算法。首先，我们关注的是数论中的核心问题： 1. **求最大公约数 (GCD)**: - 函数`gcd(a, b: integer): integer`用于计算两个整数a和b的最大公约数。该函数采用欧几里得算法，通过递归调用自身，当b为0时，返回a作为结果；否则，将b与a除以b的余数作为新的a和b继续计算。 2. **求最小公倍数 (LCM)**: - `lcm(a, b: integer): integer`函数用于求解两个整数a和b的最小公倍数。首先确保a大于或等于b，然后设置lcm等于a，接着在while循环中，只要lcm除以b有余数，就将a累加到lcm上，直到没有余数。 接下来是数论中的其他内容： - **素数检测**: - `prime(n: integer): Boolean`函数用于检查一个整数n是否为质数。它遍历2到n的平方根，如果n能被任何小于它的整数整除，则n不是质数。 - `getprime`子程序更进一步，创建了一个50000以内素数的列表，同时包含了一个`prime(x: longint)`函数，用于在给定范围内判断一个longint是否为素数。 然后，文档转向了图论部分： - **最小生成树 (Prim算法)**: - `prim(v0: integer)`是Prim算法的具体实现，用于找到图中以节点v0为中心的最小生成树。这里定义了低权值数组`lowcost`和最近节点数组`closest`，以及变量如i, j, k, min等，以进行贪心搜索和边的添加过程。 这些示例展示了C++编程在解决数学和图论问题上的实用性和效率，对于理解和实践基础算法具有很高的参考价值。通过这些代码实例，学习者可以加深对算法原理的理解，并能在实际项目中灵活应用。