质数在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。
扩展资料：
所有的奇素数都是准梅森数（2^N-1）的因 子数，则梅森合数的因子数是只有素数中的一部份。
在2^N-1的数列中，一个素数作为素因子第一次出现在指数N的数中，这个素数作为因子数在2^N-1数列中就以N为周期出现。在这种数列中指数是偶数的都等于3乘以四倍金字塔数。
在2^N-1数列中，指数大于6的，除梅森素数外，都有新增一个或一个以上的素数为因子数，新增的因子数减1能被这个指数整除。
质数的规律什么是质数？就是在所有比1大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质数，质数又叫做素数。这终规只是文字上的解释而已。能不能有一个代数式，规定用字母表示的那个数为规定的任何值时，所代入的代数式的值都是质数呢？
质数的分布是没有规律的，往往让人莫明其妙。如：101、401、601、701都是质数，但上下面的301和901却是合数。
有人做过这样的验算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有这样一个公式：设一正数为n，则n^2+n+41的值一定是一个质数。这个式子一直到n=39时，都是成立的。但n=40时，其式子就不成立了，因为40^2+40+41=1681=41*41。
被称为“17世纪最伟大的法国数学家”费尔马，也研究过质数的性质。他发现，设Fn=2^(2^n)，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65537，都是质数，由于F5太大（F5=14292967297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。但是，就是在F5上出了问题！费尔马死后67年，25岁的瑞士数学家欧拉证明：F5=14292967297=641*6700417，并非质数，而是合数。
更加有趣的是，以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。目前由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1495。这可是个超级天文数字，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。质数和费尔马开了个大玩笑！
17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：2^p-1代数式，当p是质数时，2^p-1是质数。他验算出了：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。
还剩下p=67、127、257三个梅森数，由于太大，长期没有人去验证。梅森去世250年后，美国数学家科勒证明，2^67-1=193707721*761838257287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。
现在，数学家找到的最大的梅森数是一个有378632位的数：2^1257787-1。数学虽然可以找到很大的质数，但质数的规律还是无法循通。
头五千万个质数
--------------------------------------------------------------------------------
【摘要】不按牌理出牌 数学家也拿他没办法
质数怎样分布？古今中外，不论是专业的数学家或业余的嗜好者，都曾被这问题所深深吸引。
质数是个比1大的自然数，除了自身和1以外，没有其他自然数可以除尽他。质数的分布有两个互相矛盾的特点。下面我会列举一些事实，使你永远相信这两个特点。
第一点，尽管质数的定义极为简单，又是自然数的建构砖石（任何自然数都可表为质因数的幂次的连乘积，且表法唯一），它却是数学家研究的对象中最不驯的一种；质数在自然数中，像杂草似地乱长，似乎除了机会律以外，不遵守其他的规律，没人敢说下一个会从那里冒出来。
第二点更令人惊讶，因?T篕P第一点相反，质数表现出惊人的规律性。也就是说，确有规律限制质数的行为，他们像军人一样绝对服从这些规律。
为了支持第一点，我把100以下的质数和合数写出来（除了2以外，不列偶数）：
【浏览原件】
再把1千万加减一百以内的质数列出：在9,999,900与10,000,000之间的质数
9,999,901
9,999,907
9,999,929
9,999,931
9,999,937
9,999,943
9,999,971
9,999,973
9,999,991
在10,000,000与10,000,100之间的质数
10,000,019
10,000,079
你看！没有什麼理由可以说这个数是质数，那个数不是质数。当你看到这些数字时，是否联想到宇宙的奥秘，像天边那闪烁的星星一样神秘不可测？甚至数学家都无法揭开此一奥秘，如果他们能够，他们就不会劳神苦思去计算下一个更大的质数是多少了。（没有人会想去找比前一个平方数更大的平方数，或2的幂次数——通常一个好学生只记到210=1024）。
1876年，Lucas证明2127-1为质数，这纪录维持了75年。这也难怪，因为
2127-1
=1701411834604469231731687303715884105727
直到1951年，电子计算机的新纪元，更大的质数陆续发现（见下表历次记录）。目前的记录是6002位的219937-1，不信的话，你可以去查Guiness世界记录。（编者注：根据合众国际社1978年11月15日报导，这记录已被两个18岁的加州大学学生打破。）
【浏览原件】
质数的规律
更有趣的，还是关於质数的规律。前面已提到过100以下的质数，现在用图表示，其中π(x)表示所有不大於x的质数的个数。
【浏览原件】
就这麼简单的一个图，我们已经可以看出，除了一些小的扰动以外，π(x)大致上增加得很有规律。
若把x值从一百增到五万，则此规律性变得更为明显。见下图：
【浏览原件】
当某种规律自然出现时，科学家就得设法去解释它，质数分布的规律性也不例外。关於质数分布，我们不难找到一个良好的经验规律。请看下表：（这表看来平凡无奇，却代表上千小时的艰苦计算。）
【浏览原件】
注意：x每增10倍，x与π(x)的比就增加约2.3。机警的数学家立刻联想到10取自然对数的近似值是2.3。所以x/π(x)～logx，亦即π(x)～x/logx（用log x表示x的自然对数，～表示当x接近无穷大时，π(x)与x/logx的比趋近於1；如果用≈，则表示接近的程度更好。）
质数定理
这个关系叫做质数定理，是高斯1791年发现的，但直到1896年才得到证明。高斯（1777～1855年，关於高斯与质数定理，请参阅凡异出版社，伟大数学家的一生——高斯）14岁那年收到一本对数的书；次年，研究书上所附的质数表，发现了这个定理。终其一生，高斯一直很注意质数分布，并且花了很多功夫去计算。高斯写信给他学生安克（Encke）说他「时常花费零星的片刻计算1000个连续整数（如18001到19000）中有多少质数」，最后他竟能列出三百万以下的所有质数，并且拿来和他的推测公式比较。
质数定理说π(x)是渐近地，即相对误差趋近於0，等於x/logx。但是如果拿x/logx与π(x)的图形加以比较，则可看出，虽然x/logx反映了π(x)行为的本质，却还不足以说明π(x)的平滑性。
【浏览原件】
所以，我们希望找到更佳的近似函数。如果我们再仔细看看前面那个表，会发现x/π(x)差不多恰为logx-1。经过更小心地计算，并和π(x)的更精密数据相较，乐强何（Legendre）在1808年找到特佳的近似。即
π(x)≈x/(log-1.08366)
另有一种π(x)的近似函数也不错，是高斯与质数定理同时提出的。从经验得知，当x很大时，在x附近出现质数的或然率差不多恰为1/logx。因此，π(x)差不多应为
对数和：Ls(x)=1/log2+1/log3+…+1/logx或实值上相同的
对数积分：【浏览原件】
现在再比较Li(x)与π(x)的图形，把座标轴的尺度取到这麼大时，两者完全重合。
没有必要再把乐强何的近似图形列出来给大家看，因为在0到5万之间，他的近似比Li(x)更加接近π(x)。
【浏览原件】
质数的幂次
再提一个π(x)的近似函数。从黎曼（Riemann）研究质数的结果显示，如果我们在计算质数以外，还计算质数的幂次（质数的平方算半个质数，质数的立方算1/3个质数，依此类推），则一个很大的数x为质数的或然率将更接近1/logx。从此导出
【浏览原件】
或
【浏览原件】
第二式右边的函数定名为R(x)以纪念黎曼。从下表可以看出它与π(x)有惊人的吻合。
【浏览原件】
R(x)可以表为
【浏览原件】
在这里要强调一点，高斯和乐强何的近似都是由经验归纳而来的，不是由逻辑证明得到的。甚至黎曼函数也是如此，虽然他的R(x)有理论的解释，他从未证明出质数定理。Hadamard以及de la Vall'eePoussin根据黎曼的工作，继续研究，终於在1896年首度完成证明。
孪生质数
关於质数的规律性，我们再来看一些数值的例子。前面说过，在x附近的一个数其为质数的或然率为1/logx。换句话说，假使取一以x为中心，长度为a的区间，这区间长得足以使统计成为有意义，而与x相较，又足够小时，其中质数的个数，应该约为a/logx。例如，在壹亿至壹亿零壹拾伍万之间，预计有8142个质数，因为
150,000/log(100,000,000)=150,000/18.427… ≈8142
根据同样的想法，在x附近的任意两数同时为质数的或然率应约为1/(logx)2。所以如果有人问在x到x＋a之间有多少孪生质数（连续两个奇数都是质数，如11,13或59,61），则我们可以预计有a/(logx)2个。事实上，我们可以预计多些，因为n已是质数，使n＋2为质数的可能性稍稍加大。（例如n＋2必为奇数）。用一个容易的直观的论点，可以得到在〔x,x＋a〕中，孪生质数的对数为C．a/(logx)2，此处C＝1.3203236316…。
所以在壹亿至壹亿零壹拾伍万之间应有(1.32…)．150,000/(18.427)2≈584对孪生质数。下表列出一些同长区间中质数及孪生质数的预测值及真值。由下表可以看出，理论和实际有极佳的吻合。对於孪生质数而言，这种吻合更令人惊讶。因为孪生质数是否为无穷，这问题直到现在尚无定论，遑论他的分布定律了。
【 浏览原件】
质数的距离
关於质数分布的规律性，最后一个例子就是相邻两质数的距离。若有人去查质数表，会注意到有时距离相当大。例如113和127之间无其他质数。令g（x）表x以下，所有相邻质数的最大距离。则g（200）＝127-113＝14。当然，g（x）增加得极不规则。但是用一个直觉的论点可以得到下列渐近公式，g(x)～(logx)2。从下图可以看出，像g（x）这样极不规则的函数，其行为和预测能符合的程度。
【 浏览原件】
到现在为止，质数的规律性说得较多，不规律性说得很少。而本文标题「头五千万个质数」，我也只提到前几千个而已。所以现在先列一表，比较π(x)，乐强何，高斯，黎曼四函数在x小於一千万范围内的差异。因为这四种函数在图上分辨不出差异，如前面所列π(x)与Li的比较图，所以现在这图只表示这三种函数与π(x)的差。我想从这图足以看出，一个有志研究数论的人可能遇到的麻烦有多大。当x很小时（小於一百万），x/logx-1.08366比Li（x）近似π(x)，但是五百万以后，Li（x）变得较近似，而且可以证明当x更增加时，Li（x）总是较近似π(x)。
【 浏览原件】
就算我们讨论到一千万，其中也只有60万多个质数。要达到应许的五千万个质数，x必须为十亿。下图表示十亿以内R(x)-π(x)的图形。R(x)-π(x)的振动变得愈来愈大，但即使到十亿这麼大，振动仍在几百以内。
【 浏览原件】
顺便提另一个π(x)的趣事。从图上可以看出，在一千万以内，Li（x）总是大於π(x)，10亿以内仍然如此。见下图（此图以对数尺寸绘出）。
【 浏览原件】
上图给我们一个印象，当x继续增加时，Li（x）-π(x)会稳定地无限增加。但是上述推测错了！事实上，立特伍（Littlewood）可以证明有某x值，而π(x)会大於Li（x）。但到目前为止，并未真正找到一个确数，使此事成立，而且恐怕永远不会找到。但是立特伍的证明不可能有误，而且Skewes更证明在【浏览原件】以内就有一个这样的数。英国名数学家Hardy有一次说，这可能是数学上有确定目的的数字中最大的了。总而言之，此例说明了，在质数理论里，仅仅依赖数据就想要导出结论的作法是多麼不智啊！
〔本文节译自“The First 50 million Prime Numbers”，原文刊登在The New Mathematical Intelligencer, Vol. 0, Aug. 1977，为原作者Don Zagier就任德国波昂大学教授的就任演说稿。〕
