查看“︁质数测试”︁的源代码

[[分类:数论算法]]
{{InfoBox
|name=质数测试
|eng_name=primality test
|aliases=质数检验,素性测试,素性检验
}}
'''质数测试'''/'''质数检验'''('''primality test''')指测试对一个大于 1 的[[自然数]]，测试其是否是[[质数]]的问题。有判断一个数是否是质数和找出某个数以下的有哪些质数两个变体。

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

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


{{整除与质数}}