C/C++算法实现：数论与图论

"C/C++算法实例文档包含了数论算法和图论算法的实现，具体包括求最大公约数、最小公倍数、素数判断以及最小生成树和最短路径的算法。" 在C/C++编程中，算法是解决问题的核心，它们能够帮助我们高效地处理数据和计算。以下是对文档中提及的算法进行的详细说明： 一、数论算法 1. **求两数的最大公约数 (Greatest Common Divisor, GCD)**: 提供的代码使用了欧几里得算法，该算法的基本思想是：对于任意两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数与b之间的GCD。代码中定义了一个名为`gcd`的函数，通过递归实现这一逻辑。 2. **求两数的最小公倍数 (Least Common Multiple, LCM)**: 最小公倍数可以通过两数的乘积除以它们的最大公约数得到。`lcm`函数首先检查a和b的大小，然后通过循环找到满足lcm % b == 0的最小值，即为最小公倍数。 3. **素数的求法**: - **小范围内判断一个数是否为质数**: 通过遍历从2到该数平方根的所有整数，如果n能被任何这些数整除，则它不是质数。如果所有尝试都失败，则返回true，表示n是质数。 - **判断longint范围内的数是否为素数**: 这个方法先填充一个布尔数组，标记50000以内的所有数为素数，然后从2开始，将每个素数的倍数标记为非素数。最后，存储所有的素数到数组`pr`中。`prime`函数则用于查找指定数是否在这个素数列表中。 二、图论算法 1. **最小生成树**: - **Prim算法**: Prim算法用于找到一个加权无向图的最小生成树。它从一个起始顶点开始，逐步添加边，使得每次添加的边连接的是当前生成树中的顶点和未加入树的顶点，并且这条边具有最小权重。这里的`prim`过程是一个未完整展示的过程，通常包括维护一个优先队列（如 Fibonacci堆 或者二叉堆）来选择最小权重的边。 2. **最短路径**: 文档中没有提供具体的最短路径算法，但提到了两个经典的算法：Dijkstra算法和Floyd-Warshall算法。Dijkstra算法适用于单源最短路径问题，而Floyd-Warshall则可以解决所有对之间最短路径的问题。 这些算法都是计算机科学的基础，理解和掌握它们对于解决实际问题至关重要。在C/C++中实现这些算法可以提高程序的效率，并为数据结构和算法的学习提供实践经验。