杭电ACM筛选法讲解-素数判断与优化

"杭电ppt筛选法用于ACM程序设计，讲解了如何高效地判断素数及筛选素数的方法，包括朴素算法优化和筛选法的应用。" 在ACM（国际大学生程序设计竞赛）中，高效的算法是解决问题的关键。这篇资料主要讲解了两个关于素数判断和求解的问题，以及相应的算法优化。首先，我们来看一个基础的素数判断问题。 题目描述：给定一个正整数N（1 < N < 100000），判断N是否为素数。对于这个问题，通常的朴素算法是遍历从2到N的所有数，若存在一个数能整除N，那么N就不是素数。以下是一个简单的C语言实现： ```c #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的平方根，因为一个大于平方根的因子必然对应着一个小于平方根的因子。这是优化后的代码： ```c #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开始，将所有素数的倍数标记为非素数，以此排除它们。以下是筛选法的步骤： 1. 初始化一个长度为N+1的数组，所有元素设为0，表示假设所有数都是素数。 2. 从2开始，将2的倍数全部标记为1，表示它们不是素数。 3. 移动到下一个未被标记的数（这里是3），同样将其所有倍数标记为1。 4. 重复此过程，直到遍历完所有小于等于N的数。 5. 数组中值仍为0的索引对应的数即为素数。 通过筛选法，我们可以快速找出指定范围内的所有素数，显著提高了算法效率。这种方法在处理大量素数计算或需要筛选素数的场景中非常有用，尤其在ACM等编程竞赛中，对算法的时间复杂度有较高要求时，显得尤为重要。