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

"算法大全（C，C++版）pdf文档" 在编程领域，算法是解决问题的核心，而C和C++语言则是实现算法的常用工具。本篇内容主要涵盖了数论算法和图论算法两个重要部分。 一、数论算法 1. 求两数的最大公约数（Greatest Common Divisor, GCD） 提供的代码使用了欧几里得算法（Euclidean Algorithm）来计算两个整数的最大公约数。基本思路是：对于非零整数a和b，若b|a，则GCD(a, b) = a；否则，GCD(a, b) = GCD(b, a mod b)。这种方法效率较高，时间复杂度为O(log min(a, b))。 2. 求两数的最小公倍数（Least Common Multiple, LCM） 最小公倍数可以通过两数乘积除以它们的最大公约数得到。代码中，首先确保a大于等于b，然后用a不断加a直到能被b整除，此时的a即为最小公倍数。这种方法的时间复杂度为O(1)。 3. 素数的求法 - 小范围判断素数：对于较小的数n，可以使用试除法，从2到√n遍历，若n能被其中任一数整除，则不是素数。时间复杂度为O(√n)。 - 大范围判断素数：在更大的范围内，如longint，可以预先生成一个素数表，之后判断时直接查表。这里使用了Sieve of Eratosthenes（埃拉托斯特尼筛法）来生成素数表，时间复杂度为O(n log log n)。 二、图论算法 1. 最小生成树 - Prim算法：Prim算法用于寻找图中最小生成树，从一个起点v0开始，逐步加入边，使得每次添加的边连接的是树内节点和树外节点，且权值最小。这个过程持续进行，直至所有节点都在树中。Prim算法的时间复杂度通常为O(E log V)，其中E是边的数量，V是顶点的数量。在代码中，lowcost和closest数组分别存储当前找到的最小代价和最近的邻居节点。 以上内容是算法大全（C，C++版）的部分摘录，涉及到的算法在计算机科学中具有重要地位，不仅适用于理论学习，也广泛应用于实际问题的解决，如数据压缩、加密技术、网络路由等。理解并熟练掌握这些算法，能够提升程序员解决问题的能力。