ACM编程：筛选法解决素数问题

"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竞赛中，理解并熟练运用这种算法对于快速解决问题至关重要。同时，也要注意避免那些常见的编程错误，如不必要的循环、不恰当的数据结构使用等，这些都会影响程序性能和正确性。