C/C++/Java 通用算法集合：从基础到进阶

该资源是一个综合性的算法集合，支持C，C++以及Java语言，包含多种类型的算法实现，如欧几里得算法（GCD，最大公约数）、最小公倍数（LCM）计算，素数判断算法以及图的Prim算法。 1. **欧几里得算法（GCD，最大公约数）**： - 欧几里得算法是求解两个正整数最大公约数的经典方法。代码中的`gcd`函数采用递归方式实现：如果第二个数`b`为0，则第一个数`a`就是最大公约数；否则，继续求解`b`和`a mod b`的最大公约数。这是一种基于除法的简化版本，也称为辗转相除法。 2. **最小公倍数（LCM）**： - 最小公倍数是两个或多个整数共有的倍数中最小的一个。代码中的`lcm`函数首先检查两个数的大小，确保较大的数在前，然后通过不断加较小数直到结果能被较大数整除来找到最小公倍数。这个过程使用了while循环。 3. **素数判断**： - A部分的`prime`函数用于判断一个整数是否为素数。它遍历2到输入数平方根的所有整数，如果输入数能被其中任何一个整数整除，则不是素数，返回false。如果遍历结束仍未找到因子，则输入数是素数，返回true。 - B部分的`getprime`过程生成了一个50000以内的所有素数列表，并存储在数组`p`中。首先用`fillchar`填充数组，将所有元素设为true，然后从2开始，如果一个数是素数，就将其所有的倍数标记为非素数。最后，将数组中为true的索引存入`pr`数组。 - `prime`函数利用生成的素数列表快速判断一个longint类型的大整数是否为素数，遍历已知素数列表，如果找到因子则立即返回false，否则在遍历结束后返回true。 4. **Prim算法**： - Prim算法是一种用于寻找图中最小生成树的贪心算法。在给出的`prim`过程中，`lowcost`数组记录当前节点到其他节点的最小成本，`closest`数组记录到达每个节点的最近祖先。初始时，所有节点的成本都设置为从`v0`节点出发的成本，最近祖先都设置为`v0`。随后，通过多次迭代更新这两个数组，每次都选择当前未加入树中的节点中与已加入树中的节点连接成本最低的一个，直至所有节点都被包含。 这些算法涵盖了基础数学运算、数论以及图论中的重要概念，对于学习和理解算法有很好的参考价值，无论是初学者还是有一定经验的开发者，都能从中受益。