ACM竞赛中判断素数的方法：从朴素到优化

"本文介绍了ACM竞赛中常用的几种素数判断方法，包括朴素判断、优化的循环检查以及米勒-拉宾伪素数判定等。" 在计算机科学特别是算法竞赛如ACM中，快速而准确地判断一个数是否为素数是非常重要的。素数是指大于1且仅能被1和自身整除的自然数。以下是一些常见的素数判断方法： 1. **朴素判断素数** 这是最直观的方法，也是最基础的判断方式。通过检查从2到n-1的所有整数是否能整除n来确定n是否为素数。然而，这种方法的时间复杂度较高，为O(n)，不适用于大规模数据。 ```cpp int isPrime1(int n) { if (n < 2) return 0; for (int i = 2; i <= n - 1; ++i) { if (n % i == 0) return 0; } return 1; } ``` 2. **优化的朴素判断素数** 通过将循环条件改为`i < n/2 + 1`，可以减少一半的检查次数，因为一个数的最大因子不会超过其一半。这种方法的时间复杂度仍为O(n)，但实际运行速度会有所提升。 ```cpp int isPrime2(int n) { if (n < 2) return 0; for (int i = 2; i < n / 2 + 1; ++i) { if (n % i == 0) return 0; } return 1; } ``` 3. **更优的判断素数** 使用平方根作为循环上限，进一步优化效率。因为如果n有一个因子大于其平方根，那么必定存在一个对应的因子小于或等于它的平方根。这种方法的时间复杂度降低到O(√n)。 ```cpp int isPrime3(int n) { if (n < 2) return 0; for (int i = 2; i * i <= n; ++i) { // 或者 for(int i = 2; i <= sqrt(n); ++i) if (n % i == 0) return 0; } return 1; } ``` 4. **米勒-拉宾伪素数判定** 米勒-拉宾测试是一种概率性素数判定方法，基于费马小定理。它不是确定性的，但错误率极低。对于大多数应用，经过几次测试后，可以接受结果。这种方法在处理大型数时非常有效，但可能会误判一些数为素数（称为伪素数）。 ```cpp bool MillerRabin(int n, int k) { // 实现细节略，k表示进行的测试轮数，数值越大，正确性越高 } ``` 在ACM竞赛中，通常需要根据题目限制和性能要求选择合适的方法。对于较小的数，朴素方法可能就足够了；对于较大的数，米勒-拉宾测试则更为合适。同时，还可以结合其他优化策略，如提前排除偶数（除了2以外）和某些已知的合数，以提高效率。