"ACM程序设计中的筛选法及预处理——杭州电子科技大学刘春英"
在ACM(国际大学生程序设计竞赛)中,掌握高效算法是非常关键的。本资料主要介绍了筛选法(也称为埃拉托斯特尼筛法)在素数判断和求解一系列素数问题中的应用,同时列举了菜鸟程序员常犯的错误作为警示。
首先,让我们看看一个简单的素数判断问题。题目要求输入一个整数N,判断其是否为素数,并输出相应的结果。一个朴素的算法是通过遍历从2到N的所有整数,如果N能被其中任何数整除,则N不是素数。如以下代码所示:
```cpp
#include<stdio.h>
int main() {
int i, n;
while (scanf("%d", &n) == 1) {
for (i = 2; i < n; i++) {
if (n % i == 0) break;
}
if (i == n) printf("YES\n");
else printf("NO\n");
}
}
```
然而,这个算法效率较低,对于较大的N会消耗大量时间。因此,可以优化这个算法,例如只遍历到N的平方根,因为大于平方根的因子必然对应着一个小于平方根的因子。优化后的代码如下:
```cpp
#include<stdio.h>
#include<math.h>
int main() {
int i, n, x;
while (scanf("%d", &n) == 1) {
x = (int)sqrt(n);
for (i = 2; i <= x; i++) {
if (n % i == 0) break;
}
if (i > x) printf("YES\n");
else printf("NO\n");
}
}
```
接下来,我们来看一个更复杂的问题,即求解不超过N的所有素数。朴素算法在这里显然不合适,因为它会重复计算同一个素数的倍数。这就是筛选法发挥作用的地方。筛选法的基本思想是从2开始,将所有2的倍数标记为非素数,然后找到下一个未被标记的数3,将其倍数标记,以此类推,直到所有小于等于N的数都被处理过。剩下的未被标记的数就是素数。这种方法大大减少了计算量,适用于求解一系列素数的问题。
筛选法的伪代码大致如下:
1. 初始化一个长度为N+1的数组,所有元素设为0,表示素数。
2. 从2开始,将2的所有倍数标记为1,表示非素数。
3. 找到下一个未被标记的数k(此时k一定是素数),将k的所有倍数标记为1。
4. 重复步骤3,直到k大于N。
5. 数组中值为0的索引对应的数就是素数。
筛选法是解决大规模素数问题的有效工具,它避免了重复计算,提高了算法效率。在ACM竞赛中,理解并熟练运用这种算法对于快速解决问题至关重要。同时,也要注意避免那些常见的编程错误,如不必要的循环、不恰当的数据结构使用等,这些都会影响程序性能和正确性。