质数测试

质数测试
术语名称	质数测试
英语名称	primality test
别名	质数检验, 素性测试, 素性检验

质数测试/质数检验(primality test)指测试对一个大于 1 的自然数，测试其是否是质数的问题。有判断一个数是否是质数和找出某个数以下的有哪些质数两个变体。

确认一个数是否是质数的朴素精确的质数测试算法是试除法，思路直观朴素但是需要大量计算，效率较低。当数字较大时，筛法类方法虽然需要判断更多数字，却可以减少对大数试除的次数，在判断大数是否质数时最终可能得到更高的效率。效率再高的存在一些概率性算法，这些算法一定能确认合数，但是有概率误判质数，因此通过重复次数足够多的方式概率上判断一个数是质数，如 Fermat 测试 Miller–Rabin 测试 Solovay–Strassen 测试等。

找出某数以下全部质数通常使用筛法，即 Eratosthenes 筛法。有其改进版本 Euler 筛法。

整除理论
整除关系	整除、倍数、因数	带余除法
正整数的分类	1、质数、合数
	质数测试	试除法、埃氏筛、线性筛
最大公约数理论	公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math]	辗转相除法
	互质
算术基本定理	算术基本定理	标准质因数分解