质数测试
| 质数测试 | |
|---|---|
| 术语名称 | 质数测试 |
| 英语名称 | primality test |
| 别名 | 质数检验, 素性测试, 素性检验 |
素性测试/素性检验(primality test)指测试对一个大于 1 的自然数，测试其是否是质数的问题。其包含两类不同问题：判断一个数是否是质数；找出某个数以下的有哪些质数。
出于一致性以及检索便利性考虑，本 wiki 统一在“质数”和“素数”中选择前者作为标准词条名。一般来说“一个数是否是质数”的性质称为“素性”，但是这会导致术语之间不一致，因此条目名仍然保留“质数测试”。
确认一个数是否是质数的方法分为两类：
- 试除法。思路直观朴素但是需要大量计算，效率较低。
- 概率性算法。这些算法效率更高，但是有概率误判质数，需要重复次数足够多的方式概率上判断一个数是质数，如 Fermat 测试、 Miller–Rabin 测试、 Solovay–Strassen 测试等。
找出某数以下全部质数的问题也称为质数生成(prime generation)或质数筛(prime sieving)问题，通常使用筛法，即 Eratosthenes 筛法。其一定经典改进版本为 Euler 筛法。
尽管以上两种方法本身用于解决两类不同问题，但在一些特定问题上，可能需要在两者间权衡。比如需要同时确定多个较大数字是否为质数时：直接使用试除法需要对每个待测数独立运行，其中对大数的试除必须通过完整除法完成；筛法类方法需要处理连续整数范围，但只需要执行一次即可完成。考虑到计算机执行完整除法与简单标记质数的每个倍数之间底层效率存在差异，在数字足够多、足够大的情况下，不能仅凭理论复杂度断言两个算法的实际运行效率。