素数的数目
素数是无穷多的,对这个论断,现在所已知的最古老的检验方法是欧几里德在他的几何原本中提出来的.他的检验方法可以简单地总结如下：
取有限个数的素数,因为要做自变量我们假设全部的素数都存在,将这些素数相乘然后加1,得到的数是不会被这些素数中的任何一个整除的,因为无论除哪个总会余1.因此这个数要么本身就是个素数,要么存在不在这个有限集合内的约数.因此我们开始用的集合不包含所有的素数.
别的数学家也给出了他们自己的证明.欧拉证明了全部素数的倒数和发散到无穷的.恩斯特·库默的证明尤其简洁,Furstenberg用一般拓扑证明.
尽管整个素数是无穷的,仍然有人会问“100000以下有多少个素数?”,“一个随机的100位数多大可能是素数?”.素数定理可以回答此问题.
[编辑] 寻找素数
寻找在给定限度内的素数排列,埃拉托斯特尼筛法法是个很好的方法.然而在实际中,我们往往是想知道一个给定数是否是素数,而不是生成一个素数排列.进而,知道答案是很高的概率就是已经很满意的了,用素性测试迅速地检查一个给定数（例如,有几千位数的长度）是否是素数是可能的.典型的方法是随机选取一个数,然后围绕着这个数和可能的素数N检查一些方程式.重复这个过程几次后,它宣布这个数是明显的合数或者可能是素数.这种方法是不完美的：对某些测试而言,例如费马测试,不论选取了多少随机数都有可能将一些合数判断成可能的素数,这就引出了另一种数伪素数.而像米勒-拉宾测试,虽然只要选取够多数字来检验方程式,就可以保证其检验出的质数性是正确的,但这个保证门槛的数量太过庞大,甚至比试除法所需的还要多,在有限时间内运行起来只能知道答案正确的机率很高,不能保证一定正确.
目前最大的已知素数是232582657 − 1（此数字位长度是9,808,358）,它是在2006年9月4日由GIMPS发现.这组织也在2005年12月15日发现了目前所知第二大的已知素数230402457 − 1（此数字位长度是9,152,052）.
数学家一直努力找寻产生素数的公式,但截至目前为止,并没有一个基本函数或是多项式可以正确产生所有的素数.历史上有许多试验的例子：17世纪初法国数学家梅森(Mersenne)在他的一个著作当中讨论了这样一种我们现在称之为梅森素数的素数,Mp=2p - 1,本来以为只要p是一个素数,n = 2p - 1就会是一个素数,这在p = 3,p = 5,p = 7都是正确的,但是p = 11时 }-就不是素数了.
