如何快速记忆100以内的质数(2)
素性检测
素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易(其运行时间是输入数字大小的多项式关系)。有的素性测试证明输入数字是素数，而其他测试，比如米勒 - 拉宾(Miller–Rabin )则是证明一个数字是合数。因此，后者可以称为合性测试。质数是因数只有1和它本身的数。
素性测试通常是概率测试(不能给出100%正确结果)。这些测试使用除输入数之外，从一些样本空间随机出去的数;通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小;对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到2^{-k}，可以通过增加k来使得误差尽量小。
随机素性测试的基本结构：
1.随机选取一个数字a。
2.检测某个包含a和输入n的等式(与所使用的测试方法有关)。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。
3.从1步骤重复整个过程直到达到所设定的精确程度。
在几次或多次测试之后，如果n没有被判断为合数，那么我们可以说n可能是素数。
常见的检测算法：费马素性检验(Fermat primality test)，米勒拉宾测试(Miller–Rabin primality test) ，Solovay–Strassen测试(Solovay–Strassen primality test)，卢卡斯-莱默检验法(英语：Lucas–Lehmer primality test)。
质数与素数的区别
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。
所以，质数是合数的基础，没有质数就没有合数。这也说明了前面所提到的质数在数论中有着重要地位。历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。
质数表
质数表的质数又称素数。指整数在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
用6(6N^2+6N)为界划分成一个个区间，素数的分布规律就明确显视出来了。随着区间的增大，素数的个数以波浪的形式渐渐增多。
猜你喜欢：
如何快速记忆100以内的质数(2)
