【数据结构】算法精华：最大公约数、最小公倍数与素数判断

"数据结构算法集锦，包括数论算法，如最大公约数、最小公倍数的计算，以及素数判断的实现" 在计算机科学领域，数据结构和算法是核心部分，它们对于编写高效、优化的代码至关重要。这篇算法集锦主要涵盖了一些基础但实用的数论算法，这些算法在解决数学问题以及编程竞赛如ACM或OI中经常出现。 首先，我们来看求两数最大公约数(greatest common divisor, GCD)的算法。这里采用的是欧几里得算法，也称为辗转相除法。基本思路是：两个正整数a和b，若b为0，则a是两数的最大公约数；若b不为0，则继续用a除以b的余数a mod b，然后将b替换为a，a替换为原来的余数，如此反复，直到b为0为止。这个过程可以用递归或者迭代的方式来实现，这里给出的代码是递归形式： ```pascal function gcd(a, b: integer): integer; begin if b = 0 then gcd := a else gcd := gcd(b, a mod b); end; ``` 接下来是求两数最小公倍数(least common multiple, LCM)的算法。最小公倍数可以通过两数乘积除以它们的最大公约数来得到。给定的代码中，首先确保a大于等于b，然后使用循环不断累加a，直到a能够被b整除，此时的a就是最小公倍数： ```pascal function lcm(a, b: integer): integer; begin if a < b then swap(a, b); lcm := a; while lcm mod b > 0 do inc(lcm, a); end; ``` 在素数判断方面，算法集锦提供了两种方法。第一种是判断小范围内一个数是否为质数，通过遍历2到平方根(n)之间的所有整数，如果n能被其中任何数整除，那么n不是质数。这种方法适用于较小的数： ```pascal function prime(n: integer): Boolean; var I: integer; begin for I := 2 to trunc(sqrt(n)) do if n mod I = 0 then begin prime := false; exit; end; prime := true; end; ``` 第二种方法是判断longint范围内的数是否为素数，并且可以生成一定范围内的素数表。这里使用了一个布尔数组p，初始化所有元素为true，表示所有数都被认为可能是素数。然后从2开始遍历，如果找到一个素数i，就将其所有倍数标记为非素数。这个过程会生成50000以内的素数表： ```pascal procedure getprime; var i, j: longint; p: array[1..50000] of boolean; begin fillchar(p, sizeof(p), true); p[1] := false; i := 2; while i < 50000 do begin if p[i] then begin j := i * 2; while j < 50000 do begin p[j] := false; inc(j, i); end; end; inc(i); end; end; ``` 这些基础的数论算法是学习数据结构和算法的基础，它们可以帮助我们理解更复杂的算法思想，例如动态规划、分治策略等。在实际编程中，掌握这些基础知识并能灵活运用，对于解决实际问题和提升编程能力具有极大的帮助。