NOIP竞赛算法详解：数论与素数算法

"noip备战必备算法" 在准备全国青少年信息学奥林匹克竞赛（NOIP）时，算法是至关重要的一部分。以下是一些核心的算法知识，主要涉及数论算法，包括求最大公约数（GCD）、最小公倍数（LCM）以及素数的判断。 1. **最大公约数（GCD）** GCD是两个或多个整数共有约数中最大的一个。在Pascal语言中，可以使用欧几里得算法实现。如上文所示，通过不断用较大的数除以较小的数并取余，直到余数为0，此时的除数即为GCD。这段代码中的gcd函数就是一个简单的欧几里得算法实现。 2. **最小公倍数（LCM）** LCM是两个或多个整数共有的倍数中最小的一个。通常，LCM可以通过两个数的乘积除以它们的最大公约数来计算。如上文的lcm函数，首先确保a大于等于b，然后通过while循环不断加a，直到lcm能被b整除，此时的lcm就是两数的最小公倍数。 3. **素数判断** - **小范围判断**：对于小范围内的数，可以通过遍历从2到该数平方根的所有整数，如果存在一个因子使得原数能被整除，那么它不是质数。上文中的prime函数就是这样的一个实现，当找到一个因子时立即返回false，否则返回true表示是质数。 - **大范围判断**：在更大的范围内，如判断longint类型的数是否为素数，可以采用预处理的方法，建立一个素数表。如getprime函数，初始化一个布尔数组，将所有位置标记为true，然后从2开始，将所有2的倍数标记为false，接着选择下一个未被标记的数，继续标记它的倍数，直到整个数组遍历完毕。最后，数组中值为true的位置对应的数就是素数，存入pr数组中。prime函数则用于查询这个预处理后的素数表。 这些基础的数论算法是信息学竞赛中常见的问题解决工具，特别是在处理整数性质和组合问题时。在准备NOIP的过程中，熟练掌握这些算法不仅可以提高解题速度，还能帮助选手更好地理解问题的本质。同时，了解和掌握更多高级算法，如动态规划、贪心算法、图论等，也将对参赛者有着极大的帮助。