素数

素数即质数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数(不包括0)整除的数。因为合数是由若干个质数相乘而得来的，所以，没有质数就没有合数，由此可见质数在数论中有着很重要的地位。比1大但不是质数的数称为合数。1和0既非质数也非合数。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。基于质数定义的基础之上而建立的问题有很多世界级的难题，如哥德巴赫猜想等。算术基本定理每一个比1大的数（即每个比1大的正整数）要么本身是一个质数，要么可以写成一系列质数的乘积，如果不考虑这些质数的在乘积中的顺序，那么写出来的形式是唯一的。这个定理的重要一点是，将1排斥在质数集合以外。如果1被认为是质数，那么这些严格的阐述就不得不加上一些限制条件。

素数检验

检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于根号N的所有素数去试除，若均无法整除，则N为素数，参见素数判定法则。

2002年，印度人M. Agrawal、N. Kayal以及N. Saxena提出了AKS质数测试算法，证明了可以在多项式时间内检验是否为素数。

数目计算

证明

素数的个数是无穷的。最经典的证明由欧几里得证得，在他的《几何原本》中就有记载。它使用了证明常用的方法：反证法。具体的证明如下：

●假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设 N = p1 × p2 × …… × pn，那么，N+1是素数或者不是素数。

●如果N+1为素数，则N+1要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

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

●因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。

●对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。

●所以原先的假设不成立。也就是说，素数有无穷多个。

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

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

素数、即质数，是在大于1的整数中只能被1和其自身整除的数。梅森素数以法国数学家马兰.梅森命名，指的是形如2的P次幂减一的素数，而P本身也是素数。迄今为止，数学界共计发现48个梅森素数。中央密苏里大学在2013年1月25日协调世界时间23:30:26发现的那一素数2的57,885,161次幂减一为迄今发现的最大素数。

计算

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

素数、即质数，是在大于1的整数中只能被1和其自身整除的数。梅森素数以法国数学家马兰.梅森命名，指的是形如2的P次幂减一的素数，而P本身也是素数。迄今为止，数学界共计发现48个梅森素数。中央密苏里大学在2013年1月25日协调世界时间23:30:26发现的那一素数2的57,885,161次幂减一为迄今发现的最大素数。