质数又称素数。一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除的数；否则称为合数。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。关于质数有很多历史悠久的世界级的难题，如哥德巴赫猜想，黎曼猜想，孪生素数猜想等。素数有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为素数（质数）；否则称为合数。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2。

基本信息

中文名：质数

别名：素数

外文名：priber

例子：2、3、5、7

质数个数

正在加载质数

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p，p，……，p，设n=pxpx……xp，那么，n+1是素数或者不是素数。

如果n+1为素数，则n+1要大于p，p，……，p，所以它不在那些假设的素数集合中。

如果n+1为合数，因为任何一个合数都可以分解为几个素数的积；而n和n+1的最大公约数是1，所以n+1不可能被p，p，……，p整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。

因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，则用拓扑学加以证明。

对于一定范围内的素数数目的计算

尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。

相关定理

在一个大于1的数a和它的2倍之间（即区间(a，2a]中）必存在至少一个素数。

存在任意长度的素数等差数列。（格林和陶哲轩，2004年）

一个偶数可以写成两个质数之和，其中每一个数字都最多只有9个质因数。（挪威数学家布朗，1920年）

一个偶数必定可以写成一个质数加上一个合成数，其中的因子个数有上界。（瑞尼，1948年）

一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为(1+5)(中国潘承洞，1968年)

一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为(1+2)(中国陈景润)

判定

基本判断思路

正在加载质数

在一般领域，对正整数n，如果用2到之间的所有整数去除，均无法整除，则n为质数。

python代码

java代码

php代码

c/c++代码

java代码

go代码

素性检测

素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易（其运行时间是输入数字大小的多项式关系）。有的素性测试证明输入数字是素数，而其他测试，比如米勒-拉宾（miller–rabin）则是证明一个数字是合数。因此，后者可以称为合性测试。

素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到2^{-k}，可以通过增加k来使得误差尽量小。

随机素性测试的基本结构：

1.随机选取一个数字a。

2.检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。

3.从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后，如果n没有被判断为合数，那么我们可以说n可能是素数。

常见的检测算法：费马素性检验（fer），米勒拉宾测试（erara），卢卡斯-莱默检验法（英语：luca）。

著名难题

哥德巴赫猜想

在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成三个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题“任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和“记作“a