ACM素数的几种判断方法和实现

### ACM素数的几种判断方法和实现 #### 一、朴素判断素数 素数的定义是只有两个正因数（1和自身）的大于1的自然数。判断一个数是否为素数的方法有很多，从最基本的尝试除法到更复杂的算法。 ##### 1. 最简单的朴素方法 这是最直观的方法，即遍历从2到n-1的所有数字，看是否存在能整除n的数。如果存在，则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. 改进版朴素方法 观察到一个数n不可能被大于n/2的数整除，因此可以将遍历的范围减少到2到n/2之间。这种方法的时间复杂度为O(n/2)。 ```cpp int isPrime2(int n) { if (n < 2) return 0; for (int i = 2; i <= n / 2; ++i) { if (n % i == 0) return 0; } return 1; } ``` ##### 3. 进一步优化 更进一步，我们注意到，如果n能被某个数x整除，那么n也能被n/x整除。这意味着只需要检查到√n即可。这种方法的时间复杂度为O(√n)。 ```cpp int isPrime3(int n) { if (n < 2) return 0; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return 0; } return 1; } ``` ##### 4. 最终优化版本 考虑到偶数除了2都不是素数，我们可以从3开始，每次增加2来遍历，进一步减少计算次数。 ```cpp int isPrime4(int n) { if (n < 2) return 0; if (n == 2) return 1; if (n % 2 == 0) return 0; // 增加对偶数的判断 for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) return 0; } return 1; } ``` #### 二、埃拉托斯特尼筛选法 埃拉托斯特尼筛选法是一种高效的查找指定范围内所有素数的方法。这种方法基于以下事实：一个合数必然有一个素数因子不超过它的平方根。 ##### 实现过程 1. **初始化**：创建一个包含从2到n的数组。 2. **标记非素数**：从最小的素数2开始，标记所有2的倍数为非素数；然后是3的倍数，以此类推。 3. **提取素数**：所有未被标记的数即为素数。 ```cpp vector<int> sieveOfEratosthenes(int n) { vector<bool> prime(n + 1, true); vector<int> primes; for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) { prime[i] = false; } } } for (int p = 2; p <= n; p++) { if (prime[p]) primes.push_back(p); } return primes; } ``` #### 三、米勒拉宾素数检测 米勒-拉宾算法是一种基于概率的素数检测算法，它可以在较短的时间内给出一个数是否为素数的概率性答案。 ##### 工作原理 1. **分解模运算**：将n-1表示为2^r * d的形式，其中d是奇数。 2. **随机选择a**：随机选择一个2到n-2之间的数a。 3. **计算模幂**：计算a^d mod n。 4. **判断**：若a^d mod n不为1且不为n-1，则继续进行多次乘方操作，若始终不满足条件，则n很可能不是素数。 ```cpp bool millerRabin(int n, int k = 5) { // k为测试次数 if (n <= 1 || n == 4) return false; if (n <= 3) return true; int d = n - 1; while (d % 2 == 0) d /= 2; for (int i = 0; i < k; i++) { int a = 2 + rand() % (n - 4); int x = powmod(a, d, n); if (x == 1 || x == n - 1) continue; while (d != n - 1) { x = (x * x) % n; d *= 2; if (x == 1) return false; if (x == n - 1) break; } if (x != n - 1) return false; } return true; } long long powmod(long long a, long long b, long long m) { long long result = 1; a %= m; while (b > 0) { if (b & 1) result = (result * a) % m; b >>= 1; a = (a * a) % m; } return result; } ``` ### 总结 本文介绍了ACM竞赛中常用的几种素数判断方法，从最简单的尝试除法到基于概率的米勒-拉宾算法，每种方法都有其适用场景。对于小范围的素数检测，朴素方法和埃拉托斯特尼筛选法是非常有效的；而对于大范围或需要高精度判断的情况，米勒-拉宾算法则更加适合。通过对比这些方法的特点和性能，可以根据实际需求选择最合适的技术方案。