ACM编程模板：素数筛选与随机素数测试

"编程模板，包括ACM竞赛相关的编程技巧，如素数判断和生成、随机素数测试等。" 在编程中，特别是在ACM（国际大学生程序设计竞赛）这样的高强度算法竞赛中，掌握高效的算法和数据结构是至关重要的。本资源整理了一些编程模板，这些模板可以帮助参赛者快速解决问题，提高代码效率。以下将详细解释其中涉及到的几个关键知识点： 1. **素数判断**： - 为了判断小于`MAXN`(在这里是1000010)的数是否为素数，我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这个方法的核心是通过一个布尔数组`notprime`来记录每个数是否为合数。初始化时，所有数都假定为素数（`notprime`设为`false`），然后从2开始遍历，将所有2的倍数标记为合数。接着，我们遍历到根号`MAXN`，对于每个未被标记的数`i`，将其所有倍数标记为合数。这种方法可以有效地避免溢出问题，因为一旦`i > MAXN / i`，那么`i`的倍数肯定大于`MAXN`。 2. **生成连续素数表**： - 在生成小于等于`MAXN`(这里是100000)的素数列表时，我们同样使用了埃拉托斯特尼筛法，但稍有不同。这里我们维护了一个整数数组`prime`，用来存储素数。初始时，数组元素设为0。我们遍历2到`MAXN`，对于每个未被标记的数`i`，将其作为素数加入到列表中（`prime[++prime[0]]=i`），然后更新数组，将所有`prime[j]*i`（j从1到当前已知素数个数`prime[0]`）标记为非素数。如果`i`能被当前已知的任何素数整除，我们就停止更新，因为这意味着`i`不是素数。 3. **随机素数测试**： - 有时候我们需要快速测试一个大数是否可能是素数，这就需要用到`miller`函数，它基于米勒-拉宾素性检验（Miller-Rabin Primality Test）。这个测试基于概率，它不是绝对正确的，但对于足够大的随机数，错误概率极低。函数`witness(a, n)`计算见证人`a`对数`n`的见证值。它使用了一种叫做快速幂的方法（`d=(d*d)%n`）来减少计算次数。如果在某次迭代中`d`变为1且`x`既不等于1也不等于`n-1`，则返回1表示可能不是素数。同时，根据位运算判断是否需要乘以`a`。最终，如果`d`等于1，则返回0表示`n`可能是素数，否则返回1表示可能不是素数。 这些编程模板对于ACM竞赛选手来说非常实用，它们不仅能够帮助快速解决特定类型的问题，还可以作为理解算法和数据结构的实例。在实际编程中，理解和熟练应用这些模板可以显著提升代码质量和效率。