杭电ACM筛选法讲解：从A+B到素数判断

"这篇资料是关于ACM程序设计竞赛中的筛选法及预处理技术，源自杭州电子科技大学的一份PPT，由刘春英教授讲解。主要内容包括如何判断素数、优化算法以及使用筛选法求解一系列素数问题。" 在ACM程序设计竞赛中，常常会遇到与素数相关的题目，例如计算A+B或判断一个数是否为素数。"还是以A＋B为例"这个标题可能是某个具体问题的引子，实际讨论的是更广泛的概念和算法。描述中提到的题目是要求计算两正整数之和，直到遇到两个负数为止。 首先，我们来看一个基础的素数判断问题。题目要求判断输入的N是否为素数。一个朴素的算法是遍历从2到N-1的所有数，如果N能被其中任意一个数整除，那么N不是素数。PPT中给出了一个示例代码，它使用了`for`循环和`break`语句来实现这个逻辑。但这种算法效率较低，尤其是当N非常大时。 为了优化这个算法，可以使用数学知识，只检查到N的平方根即可，因为一个大于平方根的因子必然对应一个小于平方根的因子。PPT中的第二个代码示例就采用了这种方法，通过计算`sqrt(n)`并将上限设置为`x`，减少了检查的次数，提高了效率。 接下来，题目扩展到了求解一段范围内的所有素数，例如找出所有小于等于N的素数。传统的素数判断方法在这种情况下效率低下，因为它对每个数都做一次判断。为了解决这个问题，引入了筛选法（Sieve of Eratosthenes）。筛选法的基本思想是，从2开始，将所有2的倍数标记为非素数，然后找到下一个未被标记的数（这里是3），再将其所有倍数标记，以此类推。最后，未被标记的数就是素数。这种方法可以一次性找出一个范围内所有素数，非常适合处理这类问题。 这份资料详细介绍了如何使用筛选法和预处理技巧解决ACM竞赛中的素数相关问题，包括优化的素数判断算法和筛选法求所有素数的方法。对于参加ACM竞赛或学习算法的同学来说，这些都是非常实用的知识点。