质数相关信息
概述
质数（prime，也叫素数）定义很简单：在大于1的自然数中，除了1和自身外，无法被其他自然数整除的数。但研究质数并不容易。质数的重要性在于[2]：
是所有数的基础（Primes are building blocks of all numbers.）
有特殊的性质，比如判断一个数是否质数很困难，可用于密码学
值得注意的是，1不是质数，这样的规定是为了跟算术基本原理（fundamental theorem of arithmetic）自洽。算术基本原理的内容是任何大于1的自然数均可写成质数的乘积（存在性），并且唯一（不考虑顺序的话）。如果1是质数的话，那么就会破坏算术基本原理的唯一性（想想3x1和3x1x1）。证明见维基百科的算术基本定理。
有无穷多个质数。有多种证明方法，包括欧几里得在《几何原本》给出的反证法，欧拉利用黎曼函数证明，哈里·弗斯滕伯格使用拓扑学证明。
composite指合成数
判定
素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者存在偶然不确定结果但是速度较快。
素数判定（primality tests），判断一个整数是否为素数。最直观的方法，根据定义，逐一判断从2到n−1是否是n的因数divisor（只要有，n就是合数），但这种方法效率最低，需要O(n)。
事实上，只需要检查[2,⌊n‾√⌋]就可以了。这是因为，如果n有一个大于n‾√的因数q，那么有n=p⋅q（这些数的大小关系：1,p,n‾√,q,n），这说明p也是n的一个因数，那么检查到p的时候，就可以确认n不是质数了。这种方法叫做试除法（Trial division）。
除了试除法，还有很多更复杂的判定方法，如下：
AKS test
APR test
Baillie–PSW
Elliptic curve
Pocklington
Fermat
Lucas
Lucas–Lehmer
Lucas–Lehmer–Riesel
Proth’s theorem
Pépin’s
Quadratic Frobenius test
Solovay–Strassen
Miller–Rabin
质数生成
Prime-generating，
筛选法（prime sieve）是一类快速找到质数的算法。最简单的是埃拉托斯特尼筛法（sieve of Eratosthenes，公元前250s就提出了)，
所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。
埃拉托斯特尼筛法 sieve of Eratosthenes 简称埃氏筛，也有人称素数筛。这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。
质数阶乘
素数阶乘 primorials（又称：质数阶乘）是所有小于或等于该数的素数的积，自然数n的素数阶乘，写作n#。例如10以下的素数有：2,3,5,7，所以10# = 7×5×3×2 = 210。第n个素数阶乘的值，写作pn#。例：第三个素数为5，所以p3# = 5# = 5×3×2 = 30。[1] 素数阶乘与阶乘不同于，素数阶乘是素数乘积而阶乘是自然数乘积。 素数阶乘由Harvey Dubner（英语：Harvey Dubner）定义并命名。
