拒绝访问 |
| 百度云加速
请打开cookies.
此网站 () 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(3af5-ua98).
重新安装浏览器，或使用别的浏览器素数无限多的四种证法 | 数学午餐会小组 | 果壳网 科技有意思
37906人加入此小组
今天谈的是素数无限多的证明。或许你首先想到的是欧几里得（Euclid）的那个经典证明。没错，那正是我要亮出的第一招。 【证明一】设素数有限多，那就会有全体素数有限集合。考虑，与它的某一素因子，显然，不会是任何一个（为什么？自己想。）已经是全体的素数，却没有包括，矛盾，前提“素数有限多”不成立。▋该证明是官方课本上用到烂的那招，相信大家早已不满足于此。因此，今天，我从某“天书”上摘来另三种完全不同的证明。不多说喽，相信大家等不及了，开始吧。 【证明二】用上费马数（Fermat 数）的时候到了。费马数是指形如的。（本段中为任意正整数）由于费马数无限多，只要证明任意两个费马数互素，则必有无穷多个素数。先给一个关系式：如果这一关系成立，设和的某一公因子为；如此便存在正整数、，使左边等于，右边等于；左边减右边得，整除2，可推断为1或2；【此处错误的修正感谢果壳网友 】由于费马数都是奇数，不可能为2。即得与互素。于是，验证这一关系式即可说明任意两费马数互素。可以用数学归纳法证明该关系成立。时，，， 关系成立；由归纳假设，到时关系成立，下面证明时关系也成立：证毕。▋ 【证明三】接下来要用上的是素数函数，它定义的是不超过实数的素数个数。另引入由定义的自然对数，考虑自然对数与调和级数的关系，当时有此处的表示对所有仅含素因子的求和。举例，当取64.82时，中间一项即前自然数倒数和，取64；而后面一项取所有小于等于64的素数们作因子所组成的一些正整数的倒数的累和（绕口的），这个m虽然有无穷多个，但这个累和可能收敛。如此一来，每一个m都可表示为形式。可写成上式括号里是一个几何级数，因此（是之前提到的素数计数函数）显然，，所以如你所知，自然对数函数无界，因而素数计数函数也无界，素数无穷多。▋接下来的第四个证明，用上的同样是级数。证明四的特别之处在于它不仅证明了素数无限多这个主命题，还顺便给出全体素数各自的倒数的累和发散这一结论，挺强大的。但是证明四的推算将会复杂一些，往下看有一点心理准备与耐心。 【证明四】若能得证“全体素数各自倒数的累和”即发散，那么素数无限多也自然得证。现先假设该级数收敛。那么一定存在自然数使得。我们称此时的为“小素数”；为“大素数”。这样对于任意自然数 N，都有设表示满足且至少含一个大素数为因子的正整数；为满足且因子都是小素数的正整数的个数。这样说来，应该是等于的吧。然而，我们可以找到这么一个N，使得。注意到，可以作为满足的的倍数们的计数公式。于是再看。每个小于或等于的都可以写成的形式（为什么？我也想知道……）。是没有平方因子的部分，也就是一些互异的小素数的乘积；按组合数学的分步乘法计数原理，逐个审查每一个小素数有没有被使用，得一共有种可以有的组合。而，至多有个不同的平方部分。所以有对于任意的都成立，我们只需要找到一个小于或等于的即即可。解不等式，得使得，与题设矛盾。矛盾的原因在于并不成立；也即级数应发散。▋ 好啦，不同的证明已经给出了三个，其实原本书上还有两个证明的；但由于用的是拓扑与近世代数，我才疏学浅，看不懂，就懒得照抄搬上来了。这里和书上给出了这个谜语的六种不同的解谜方式；然而，这一谜语在我们的世界上，岂止六种解题方式，我记得的起码都数千种了！素数无限多、勾股定理、等面积拼接等这些脍炙人口的数学证明问题，一向都是数学爱好者们的“出气筒”。下次，看看再谈其他的吧。 ————————————————文中证明全部摘自数学书籍《》
+ 加入我的果篮
拓扑那个证明可以看看。说是拓扑，其实用到的只是集合论。没学过拓扑应该也能读懂。
matrix67的博客还给出了一些别的证明，可以到那里翻一翻。
文字游戏小组管理员
我也来四个证法..反设只有有限个p1,...,pk..I.考虑2p1p2...pk+1.II.考虑3p1p2...pk+1.III.考虑4p1p2...pk+1.IV.考虑5p1p2...pk+1.LOL
应用数学专业
引用 的话：也来四个证法..反设只有有限个p1,...,pk..I.考虑2p1p2...pk+1.II.考虑3p1p2...pk+1.III.考虑4p1p2...pk+1.IV.考虑5p1p2...p...V.考虑6p1p2...pk+1VI.考虑7p1p2...pk+1…………
应用数学专业
引用 的话：拓扑那个证明可以看看。说是拓扑，其实用到的只是集合论。没学过拓扑应该也能读懂。是的，看上去像是集合论的方法，虽然我还是不懂。昨天我本已经敲进去了的！可惜草稿悲剧性丢失，就作罢了……等不用上学空余了再贴上，连同代数那个。代数那个很短很简洁，只是我看不懂。
应用数学专业
写完本文，有种喘不过气的感觉。本来公式推算就不算简单，加上果壳的排版把它们堆得一上一下的，自己都被吓到了。有谁能像发帖人我一样从头读到尾的，我得膜拜一个，你真难得！TOT
应用数学专业
引用 的话：matrix67的博客还给出了一些别的证明，可以到那里翻一翻。Matrix67大神博文《》，你说的是这篇，是吗？看了一下， 博文中的证法的确非常简洁漂亮通俗易懂有趣好玩。很值得有兴趣的人一看，这里就顺便附上链接了。
这本书买了一直没看……英语影印版本的太蛋疼了……
应用数学专业
引用 的话：这本书买了一直没看……英语影印版本的太蛋疼了……我的是中译版欧也╮(╯▽╰)╭
天书证明么。。
好吧我无视了最后一行。。
可以考虑用欧拉恒等式证明，哦。。好像就是第三个。。
应用数学专业
引用 的话：可以考虑用欧拉恒等式证明，哦。。好像就是第三个。。是的，就是用上素数计数函数这个。\(≧▽≦)/
引用 的话：是的，就是用上素数计数函数这个。\(≧▽≦)/可以顺带介绍欧拉公式。。另：用另一个欧拉公式，以及和这个欧拉公式类似的思想可以求出zeta（2n），n为正整数
数学/化学爱好者
相邻的整数互质，所以2和3互质。然后2*3=6和6+1=7互质。然后6*7=42和42+1=43互质。然后42*43=+1=1807互质。以此类推也可以得到无穷多两两互质的整数。
应用数学专业
引用 的话：邻的整数互质，所以2和3互质。然后2*3=6和6+1=7互质。然后6*7=42和42+1=43互质。然后42*43=+1=1807互质。以此类推也可以得到无穷多两两互质的整...嗯嗯嗯，Matrix67博客的证法就是这个呢呢呢
应用数学专业
接下来我只负责搬运余下的两个证明，证明内容概不负责，抽象代数与拓扑，我还不懂 ==【证法五】设有限且令 p 为最大的素数。我们考虑梅森数（Mersenne数），并证明的任意素因子 q 皆大于 p ，由此导出素数无限多。令 q 为整除的一个素数，则有。因为 p 为素数，前一公式说明在域的乘法群中元素 2 的阶就是 p 。而该乘法群有 q-1 个元素。由拉格朗日定理（Lagrange定理），我们得到 p | (q-1) 并由此可以导出 p&q 。▋
开始我也看不懂群论的那个证明，于是我就去找了群论的资料学习了一下。楼主没有扩展知识的习惯啊
应用数学专业
【证明六】考虑数集上的一种奇特的拓扑。对a,b∈，b&0，令每个集合都是正负无界的算术级数。我们称集合为开集，如果是空集，或者对任意的 a∈都存在 b&0 使得。显然，开集的并总是开集。另外，如果和是两个开集，对任意的，，以及。，都有。所以开集的有限交是开的。从而我们定义的开集族的确导出了上的一个拓扑。这里我们注意两个事实：【A】每个非空的开集都是无界的【B】每个都是既开又闭的第一点是显然的。至于第二点，我们观察这说明是开集的补，因而是闭集。素数在哪里呢？下面就来了——每个整数 n≠1,-1 都有某个素因子 p ，所以我们有 n∈以及如果是有限的，那么将是有限个闭集的并（根据【B】），所以是闭的，进而导出是个开集，这与【A】矛盾。▋
应用数学专业
引用 的话：开始我也看不懂群论的那个证明，于是我就去找了群论的资料学习了一下。楼主没有扩展知识的习惯啊只要明白域的概念应该就能看懂了……这就顺手找找==
引用 的话：只要明白域的概念应该就能看懂了……这就顺手找找==虽然说了域，但是根本没用域的性质，只是抽出了乘法群。。。。
应用数学专业
引用 的话：虽然说了域，但是根本没用域的性质，只是抽出了乘法群。。。。还是没懂是什么，据网上说的，伽罗瓦域？
引用 的话：还是没懂是什么，据网上说的，伽罗瓦域？就是个模算数，Zq里面只有0到q-1这些数字。运算结果对q取模。比如我在Z11中7+8=4。在Z17中8+9=0。
引用 的话：还是没懂是什么，据网上说的，伽罗瓦域？可以参考这个：对群论的介绍，解释了拉格朗日定理
每次看到你发帖我都感觉是在炫耀ID啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊这是病么……
应用数学专业
引用 的话：可以参考这个：对群论的介绍，解释了拉格朗日定理太赞了。顺便学学阅读满屏的英文术语 ==引用 的话：每次看到你发帖我都感觉是在炫耀ID啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊这是病么……是的。不是16个啊后面那句啊，而是前面的那句，正解了。微博上没抢到，在豆瓣果壳上爽了一把。
还有一种下法,哥德巴赫猜想是正确的话,那么无穷多的自然数,必然需要无穷多的素数
还是考虑数学界还没有证明的问题，更有一些意思重复别人做过的证明，意义不是太大
数学/化学爱好者
引用 的话：还有一种下法,哥德巴赫猜想是正确的话,那么无穷多的自然数,必然需要无穷多的素数你这是在用费马大定理证明2的立方根不是有理数……
全体素数的倒数和，用素数定理做近似计算法，把第n个素数近似等于nlogn，很容易算出此数值大致等于loglogn也就是说求全体素数的倒数和，是一个很一般的问题。但是要求解所有的孪生素数对的倒数和，是否收敛就没有那么容易了，貌似要用到BRUM筛法，才得出该倒数和是收敛的
引用 的话：可以考虑用欧拉恒等式证明，哦。。好像就是第三个。。第三个不是欧拉恒等式的证明欧拉恒等式是Π（1-p**（-s））**（-1）=∑n**(-s)黎曼把欧拉恒等式扩大到复数域，就基本上得出了素数定理的证明，当然严格的证明在大约50年以后才给出这∑n**(-s)也就成为了在解析数论领域中最为经典的函数，如果你能够证明这个函数的零点的实部都等于0.5，那么你绝对比那个证明哥德巴赫猜想的人还要不得了，甚至比证明费马大猜想的人还要不得了，这个猜想即黎曼猜想是一百多年来可以说没有丝毫进展的一个猜想。
引用 的话：第三个不是欧拉恒等式的证明欧拉恒等式是Π（1-p**（-s））**（-1）=∑n**(-s)黎曼把欧拉恒等式扩大到复数域，就基本上得出了素数定理的证明，当然严格的证明在大约50年以后才给出这∑...不用这么fancy，你再仔细想想，其实他就是用欧拉恒等式，然后用到你从右侧接近1的时候，zeta（s）趋向于无穷，不用延拓什么的。。。
应用数学专业
引用 的话：第三个不是欧拉恒等式的证明欧拉恒等式是Π（1-p**（-s））**（-1）=∑n**(-s)黎曼把欧拉恒等式扩大到复数域，就基本上得出了素数定理的证明，当然严格的证明在大约50年以后才给出这∑...引用 的话：不用这么fancy，你再仔细想想，其实他就是用欧拉恒等式，然后用到你从右侧接近1的时候，zeta（s）趋向于无穷，不用延拓什么的。。。以前读欧拉等式是在一本叫《素数之恋》的书，花了100多页弄这式子，华丽得很……所以我忘了证法，因此证法欠奉了 ==不用扩展到复数域那形式，谁可以先给一个欧拉等式的证法啊……百度与维基一搜都是那个e^πi+1=0
应用数学专业
引用 的话：你这是在用费马大定理证明2的立方根不是有理数……用结论证明前提……
引用 的话：以前读欧拉等式是在一本叫《素数之恋》的书，花了100多页弄这式子，华丽得很……所以我忘了证法，因此证法欠奉了 ==不用扩展到复数域那形式，谁可以先给一个欧拉等式的证法啊……百度与维基一搜都是那...证明应该挺简单的吧，你看一边是连和，另一边是连乘的形式，首先你要弄明白连乘的收敛的语言，然后你就证明把这两个式子都写成有限和与有限乘积的形式，然后比较大小，你证明互相能控制，然后你就得到了他们相等了(当证明了和式是收敛的时候)
引用 的话：以前读欧拉等式是在一本叫《素数之恋》的书，花了100多页弄这式子，华丽得很……所以我忘了证法，因此证法欠奉了 ==不用扩展到复数域那形式，谁可以先给一个欧拉等式的证法啊……百度与维基一搜都是那...你可以下载潘承洞潘成彪的《解析数论基础》在介绍，Dirichlet级数的这一章就给出了欧拉等式的证明主要是因为（1-p**(-s))**(-1)=1+p**(-s)+p**(-2s)+p**(-3s)+.......然后当p取遍各个数值的时候，连乘的结果就走遍了n**（-s)的各个值，当然两者的差还有一个余项，可以证明该余项当n无穷的时候，余项等于0，因此两者相等这个欧拉等式还有推广，具体可以看潘氏兄弟的那本书拓展到复数域是因为用复变函数积分起来比较容易，就是画一个圈，在这个圈圈里面的积分就与零点极点有关，所以解析数论到最后就变成讨论各种形式的Dirichlet级数的零点了
应用数学专业
引用 的话：证明应该挺简单的吧，你看一边是连和，另一边是连乘的形式，首先你要弄明白连乘的收敛的语言，然后你就证明把这两个式子都写成有限和与有限乘积的形式，然后比较大小，你证明互相能控制，然后你就得到了他们相等了...其实我的《离散数学》课本里集合论一章包含排斥原理一段也有它的简接证明——但涉及到集合交并的概念，感觉画蛇添足了。引用 的话：你可以下载潘承洞潘成彪的《解析数论基础》在介绍，Dirichlet级数的这一章就给出了欧拉等式的证明主要是因为（1-p**(-s))**(-1)=1+p**(-s)+p**(-2s)+p**(-3...比较来还是这一个原始证明最简洁。
数学/化学爱好者
引用 的话：用结论证明前提……不是。。如果你在证明哥德巴赫猜想的时候没有用到质数无穷多或者这个结论的推论，那就不算是循环论证。。
引用 的话：其实我的《离散数学》课本里集合论一章包含排斥原理一段也有它的简接证明——但涉及到集合交并的概念，感觉画蛇添足了。比较来还是这一个原始证明最简洁。晕。。我是在讲这种证明的大体思路啊。。。还是推荐Stein的复分析。。解析数论什么的，感觉还是不如代数数论发展的好
应用数学专业
引用 的话：不是。。如果你在证明哥德巴赫猜想的时候没有用到质数无穷多或者这个结论的推论，那就不算是循环论证。。对哦，不一定会用上的哦……
引用 的话：你这是在用费马大定理证明2的立方根不是有理数……呃,虽然费马大定理能不能证姑且不率,你这个比方还算比较贴切的,我接受.
科学松鼠会成员，信息学硕士生
引用 的话：晕。。我是在讲这种证明的大体思路啊。。。还是推荐Stein的复分析。。解析数论什么的，感觉还是不如代数数论发展的好主要是解析数论感觉像是一堆技巧堆起来……不是说做不出来东西，但是做出来在感觉上也很奇怪……
数学/化学爱好者
引用 的话：呃,虽然费马大定理能不能证姑且不率,你这个比方还算比较贴切的,我接受.费马大定理94年就证明完了，都出书了，两百多页的。
引用 的话：费马大定理94年就证明完了，都出书了，两百多页的。我没说完整,我意思是费玛大定理能不能用来证2的立方根是不是有理数.
只看懂了第一个
数学/化学爱好者
引用 的话：我没说完整,我意思是费玛大定理能不能用来证2的立方根是不是有理数.能啊反证法：假设2的立方根是有理数，则存在两个整数非零p，q使得(p/q)^3=2也就是p^3=2*q^3=q^3+q^3也就是说(q,q,p)是方程x^3+y^3=z^3的一组非零整数解，与费马大定理矛盾。证毕。
引用 的话：主要是解析数论感觉像是一堆技巧堆起来……不是说做不出来东西，但是做出来在感觉上也很奇怪……主要是modular function来做，但是现在复分析技巧已经发展的差不多了，现在需要的是对群作用的描述来改进，然后反正还是感觉代数才是描述了这个环的结构会比较可能点，而且现在代数几何发展这么猛，包括Grothendieck那一套，所以在可以预见的未来里应该还是代数方法占上风
麻烦问下欧拉那个证明中“每个被求和的m可以唯一地表示为（连乘）形式“是怎么回事啊？
麻烦问下欧拉那个证明中“每个被求和的m可以唯一地表示为（连乘）形式“是怎么回事啊？
引用 的话：证明三吗？质因数分解？
(C)2017果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号&&&&
违法和不良信息举报邮箱：&&&&举报电话：质数 - 搜狗百科
&&历史版本
该版本已锁定
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。因为合数是由若干个质数相乘而得来的，所以，没有质数就没有合数，由此可见素数在数论中有着很重要的地位。质数是与合数相对立的两个概念，二者构成了数论当中最基础的定义之一。算术基本定理每一个比1大的数（即每个比1大的正整数）要么本身是一个素数，要么可以写成一系列素数的乘积，如果不考虑这些素数的在乘积中的顺序，那么写出来的形式是唯一的。这个定理的重要一点是，将1排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件。
只有1和它本身两个正因数的自然数，叫质数(Prime Number)。（如：由2÷1=2，2÷2=1，可知2的因数只有1和它本身2这两个约数，所以2就是质数。与之相对立的是合数：“除了1和它本身两个因数外，还有其它因数的数，叫合数。”如：4÷1=4，4÷2=2，4÷4=1，很显然，4的因数除了1和它本身4这两个因数以外，还有因数2，所以4是合数。）100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。注：（1）2和3是所有素数中唯一两个连着的数。（2）2是唯一一个为偶数（双数）的质数。
证明质数质数的个数是无穷的。最经典的证明由欧几里得证得，在他的《几何原本》中就有记载。它使用了证明常用的方法：反证法。具体的证明如下：●假设质数只有有限的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个梅森素数。中央密苏里大学在日协调世界时23:30:26发现的那一素数2的57,885,161次幂减一为迄今发现的最大素数。检验素数检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于根号N的所有素数去试除，若均无法整除，则N为素数，参见素数判定法则。2002年，印度人M. Agrawal、N. Kayal以及N. Saxena提出了AKS质数测试算法，证明了可以在多项式时间内检验是否为素数。
　　现在，数学家找到的最大的梅森数是一个有9808357位的数：2^。数学虽然可以找到很大的质数，但质数的规律还是无法循通。　30000以内的质数表　　2 3 5 7 11 13 17 19 23 29 31 37 41 43 47　　53 59 61 67 71 73 79 83 89 97 101 103 107 109 113　　127 131 137 139 149 151 157 163 167 173 179 181 191 193 197　　199 211 223 227 229 233 239 241 251 257 263 269 271 277 281　　283 293 307 311 313 317 331 337 347 349 353 359 367 373 379质数　　383 389 397 401 409 419 421 431 433 439 443 449 457 461 463　　467 479 487 491 499 503 509 521 523 541 547 557 563 569 571　　577 587 593 599 601 607 613 617 619 631 641 643 647 653 659　　661 673 677 683 691 701 709 719 727 733 739 743 751 757 761　　769 773 787 797 809 811 821 823 827 829 839 853 857 859 863　　877 881 883 887 907 911 919 929 937 941 947 953 967 971 977　　983 991 997 19 33 51 69　　93 09 29 63 87　　13 29 49 79 91　　03 21 67 99 27　　39 53 81 89 11　　43 59 79 01 13　　27 63 93 09 33　　53 83 01 31 67　　77 01 31 51 87　　99 17 39 69 87　　11 31 43 79 13　　39 67 81 97 33　　47 71 83 99 23　　47 73 21 43 57　　93 21 57 71 87　　99 13 31 53 89　　01 33 51 79 03　　27 57 71 11 37　　61 83 19 63 81　　03 21 53 71 07　　23 43 61 89 13　　57 67 99 27 39　　57 81 07 23 43　　73 97 19 39 69　　97 23 51 77 07　　19 31 67 03 19　　49 73 93 27 39　　59 11 29 43 61　　83 27 49 73 09　　41 57 83 13 23　　61 91 21 43 57　　79 21 33 83 93　　13 61 89 19 37　　57 73 99 11 39　　77 99 13 53 79　　09 33 73 97 23　　51 93 13 31 43　　77 01 19 31 69　　91 41 53 69 93　　17 43 83 07 27　　49 61 79 03 39　　87 29 47 73 91　　21 43 73 03 21　　57 71 99 17 37　　59 73 97 49 73　　21 51 69 81 19　　59 79 01 19 61　　81 03 29 57 71　　07 47 61 77 97　　19 43 79 21 51　　87 11 29 47 97　　21 49 93 33 59　　87 07 29 47 61　　83 03 39 69 87　　03 27 57 93 29　　67 79 07 33 51　　09 39 69 89 11　　47 71 09 31 43　　73 93 17 63 87　　23 43 67 21 39　　73 99 27 47 77　　93 13 37 53 83　　19 37 61 87 29　　51 71 07 29 49　　91 27 51 73 99　　21 41 81 11 37　　49 91 13 31 39　　67 91 21 47 01　　23 43 77 97 33　　49 81 03 29 51　　71 01 29 49 007　　
21799质数　　
　　古老的筛法可快速求出以内的所有素数（质数）。　　筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。　　具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）　　程序　　#include&stdio.h&　　#include&time.h&　　#define MAX 　　int n,p[MAX],tot=0;　　double s,t;　　FILE *质数　　void prime()　　{ int i,j,t=sqrt(n)+1;　　for(i=2;i&t;i++)　　if(p)　　{ fprintf(fp,&%d\n&,i);　　tot++;　　j=i+i;　　while(j&n)　　{ p[j]=0;　　j+=i;　　}　　}　　for(i=t+1;i&n;i++)　　if(p)　　{ tot++;　　fprintf(fp,&%d\n&,i);　　}　　}　　main()　　{　　fp=fopen(&prime.txt&,&w&);　　scanf(&%d&,&n);　　s=clock();　　for(i=0;i&n;i++)　　p=1;　　prime();　　t=clock();　　fprintf(fp,&Num = %d\nTime = %.0lf ms\n&,tot,t-s);　　fclose(fp);　　}　　本机测试结果：用时1156ms（1.156秒）　　用时80秒（较慢，主要是内存太少，反复读硬盘的原因）
　　1 朴素筛法，就是直接试除　　2 若a是n的因子，那么n/a也是n的因子，所以如果n有一个大于1的真因子，则必有一个不大于n的1/2次方的因子　　3 进一步的，如n是合数，他必有一个素因子不大于n的1/2次方，如要检测一个m以内的数是否为素数需事先建立一个m的1/2次方以内素数表。　　4 Miller-Rabbin算法　　5 概率算法　　6 无条件的素数测试（包含APR算法 Jacobi sum测试 等）　　7.n的n次幂除以n，若余数为2，则n为质数
8.素数（除2和3）一定是6k±1（k∈Z）中。　　......　　效率比较：　　效率比较一般的有 Eraosthenes氏筛选法　　效率较高的有　　Jacobbi Sums测试　　更好的有　　Miller-Rabbin算法(Monte-Carlo系列的算法)　　不过这个是概率算法,依赖于 ERH(extend Riemann Hypothesis)　　现在使用的素数判定算法还有　　Unconditional Primality Test(基于Algebraic Number Theory)　　近15年来还有椭圆曲线算法，　　APR, Random Curve, Abelian Variety测试关于编程语言中对素数判断的说明及证明质数　　即只需用2到根号N之间的所有整数去除N就可以证明N是否为素数)：　　证明：假设　　N　　从2到根号N都没有它的因数　　而他有一个因数是m并且是大于根号N　　很显然有：N/m = n（一个整数），由于m&根号N，n&根号N　　这说明N从2到根号N有它的因数　　与假设相反
　　根据素数定理，素数平均分布稠密程度π(x)/x≈1/lnx，对于512位大整数，随机产生为素数概率约为1/355，继而我们对每个随机数利用Miller-Rabbin测试，不断选取基b，计算是否每次都有bn-1 mod n=1都成立，则n几乎肯定是素数。由于多次运行后出错概率非常小，在实际中是可以信赖的。在Java里，BigInteger类提供的isProbablePrime()函数帮助简化了测试操作。　　代码仅供参考，属于概率型，不保证求出的都是质数。　　bool miller-rabin(unsigned char *n,int len)　　{　　unsigned char *a,*b,*c;　　int la,lb,i,　　a=GetRInt(2);　　la=2;　　lb=　　b=new unsigned char[len];　　c=　　lc=1;　　c[0]=1;c=0;　　for(i=0;i&i++)　　b=n;　　i=0;　　while(1)　　{　　if(b==0)　　{　　b=255;　　i++;　　}else　　{　　b--;　　　　}　　}　　while(lb!=0)　　{　　if(b[0]%2!=0)　　{　　c=Mul(a,c,la,&lc);　　mod(c,n,&lc,len);　　}　　div2(b,&lb);　　a=Square(a,&la);　　mod(a,n,&la,len);　　}　　if(lc==1&&c[0]==1)　　　　素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3×5，所以15不是素数；又如，12＝6×2＝4×3，所以12也不是素数。另一方面，13除了等于13×1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。　　有的数，如果单凭印象去捉摸，是无法确定它到底是不是素数的。有些数则可以马上说出它不是素数。一个数，不管它有多大，只要它的个位数是2、4、5、6、8或0，就不可能是素数。此外，一个数的各位数字之和要是可以被3整除的话，它也不可能是素数。但如果它的个位数是1、3、7或9，而且它的各位数字之和不能被3整除，那么，它就可能是素数（但也可能不是素数）。没有任何现成的公式可以告诉你一个数到底是不是素数。你只能试试看能不能将这个数表示为两个比它小的数的乘积。　　找素数的一种方法是从2开始用“是则留下，不是则去掉”的方法把所有的数列出来（一直列到你不想再往下列为止，比方说，一直列到10，000）。　　第一个数是2，它是一个素数，所以应当把它留下来，然后继续往下数，每隔一个数删去一个数，这样就能把所有能被2整除、因而不是素数的数都去掉。在留　　下的最小的数当中，排在2后面的是3，这是第二个素数，因此应该把它留下，然后从它开始往后数，每隔两个数删去一个，这样就能把所有能被3整除的数全质数　　都去掉。下一个未去掉的数是5，然后往后每隔4个数删去一个，以除去所有能被5整除的数。再下一个数是7，往后每隔6个数删去一个；再下一个数是11　　，往后每隔10个数删一个；再下一个是13，往后每隔12个数删一个。……就这样依法做下去。　　你也许会认为，照这样删下去，随着删去的数越来越多，最后将会出现这样的情况；某一个数后面的数会统统被删去崮此在某一个最大的素数后面，再也不　　会有素数了。但是实际上，这样的情况是不会出现的。不管你取的数是多大，百万也好，万万也好，总还会有没有被删去的、比它大的素数。　　事实上，早在公元前300年，希腊数学家欧几里得就已证明过，不论你取的数是多大，肯定还会有比它大的素数，假设你取出前6个素数，并把它们乘在　　一起：2×3×5×7×11×13＝30030，然后再加上1，得30031。这个数不能被2、3、5、7、11、13整除，因为除的结果，每次都会余1。如果30031除了自己以外不能被任何数整除，它就是素数。如果能被其它数整除，那么30031所分解成的几个数，一定都大于13。事实上，3　　9。　　对于前一百个、前一亿个或前任意多个素数，都可以这样做。如果算出了它们的乘积后再加上1，那么，所得的数或者是一个素数，或者是比所列出的素数还要大的几个素数的乘积。不论所取的数有多大，总有比它大的素数，因此，素数的数目是无限的。　　随着数的增大，我们会一次又一次地遇到两个都是素数的相邻奇数对，如5，7；11，13；17，19；29，31；41，43；等等。就数学家所能及的数来说，它们总是能找到这样的素数对。这样的素数对到底是不是有无限　　个呢？谁也不知道。数学家认为是无限的，但他们从来没能证明它。这就是数学家为什么对素数感兴趣的原因。素数为数学家提供了一些看起来很容易、但事实　　却非常难以解决的问题，他们目前还没能对付这个挑战哩。　　【素数的程序】　　for i=1 to 100　　for j=2 to i　　if j=i　　?i　　endif　　if mod(i,j)=0　　EXIT　　endif　　endfor　　endfor
2是唯一一个既是素数又是偶数的数。
素数定理素数定理描述素数的大致分布情况。 素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x)为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。 π(x)≈x/ln x 其中ln x为x的自然对数。上式的意思是当x趋近∞，π(x) 和x/ln x的比趋 近1（注：该结果为高斯所发现）。但这不表示它们的数值随着x增大而接近。 下面是对π(x)更好的估计： π(x)=Li (x) + O (x e^(-(ln x)^(1/2)/15)，当 x 趋近∞。 其中 Li(x) = ∫(dt/ln x2,x)，而关系式右边第二项是误差估计。素数定理可以给出第n个素数p(n)的渐近估计：p(n)～n/ln n. 它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。 这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(Jacques Hadamard)和比利时数学家普森(Charles Jean de la Vallée-Poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。 因为黎曼ζ函数与π(x)关系密切，关于黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家Helge von Koch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为 :π(x)=Li (x) + O (x^(1/2) ln x) 至於大O项的常数则还未知道。素数定理有些初等证明只需用数论的方法。第一个初等证明于1949年由匈牙利数学家保罗·艾狄胥（“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。 在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些问题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。Selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。 但是，有必要指出的是，虽然该初等证明只用到初等的办法，其难度甚至要比用到复分析的证明远为困难。质数算术基本定理任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 这里P_1&P_2&...&P_n是质数，其诸方幂 ai 是正整数。这样的分解称为N 的标准分解式。算术基本定理的内容由两部分构成：分解的存在性、分解的唯一性（即若不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的）。算术基本定理是初等数论中一个基本的定理，也是许多其他定理的逻辑支撑点和出发点。此定理可推广至更一般的交换代数和代数数论。高斯证明复整数环Z[i]也有唯一分解定理。它也诱导了诸如唯一分解整环，欧几里得整环等等概念。 更一般的还有戴德金理想分解定理。素数等差数列等差数列是数列的一种。在等差数列中，任何相邻两项的差相等。该差值称为公差。类似7、37、67、97、107、137、167、197。这样由素数组成的数列叫做等差素数数列。2004年，格林和陶哲轩证明存在任意长的素数等差数列。日，两人宣布：他们证明了“存在任意长度的素数等差数列”，也就是说，对于任意值K，存在K个成等差级数的素数。例如 K=3，有素数序列3, 5, 7 （每两个差2）……K=10，有素数序列 199, 409, 619, 829, , ,
（每两个差210）。定理在一个大于1的数a和它的2倍之间（即区间(a, 2a]中）必存在一个素数。存在任意长度的素数等差数列。（格林和陶哲轩，2004年）一个偶数可以写成两个数字之和，其中每一个数字都最多祇有9个质因数。（挪威数学家布朗，1920年）一个偶数必定可以写成一个质数 p 加上一个合成数 c ，其中 c 的因子个数有上界。（瑞尼，1948年）一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 (1 + 5) (中国潘承洞，1968年)一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2) (中国陈景润)未解之谜哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？斐波那契数列内是否存在无穷多的素数？是否存在无穷多的梅森素数？在n2与（n+1）2之间是否每隔n就有一个素数？是否存在无穷个形式如X2+1素数？黎曼猜想
哥德巴赫猜想在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成三个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题&任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和&记作&a+b&。1966年陈景润证明了&1+2&成立，即&任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和&。　今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。从关于偶数的哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。若哥德巴赫猜想尚未完全解决，但1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”，数学家认为弱哥德巴赫猜想已基本解决。质数黎曼猜想黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想，由数学家波恩哈德·黎曼（）于1859年提出。德国数学家希尔伯特列出23个数学问题．其中第8问题中便有黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出：黎曼ζ函数ζ(s)非平凡零点（在此情况下是指s不为-2、-4、-6等点的值）的实数部份是1/2。即所有非平凡零点都应该位于直线1/2 + ti（“临界线”（critical line））上。t为一实数，而i为虚数的基本单位。至今尚无人给出一个令人信服的关于黎曼猜想的合理证明。在黎曼猜想的研究中，数学家们把复平面上 Re(s)=1/2 的直线称为 critical line。 运用这一术语，黎曼猜想也可以表述为：黎曼ζ 函数的所有非平凡零点都位于 critical line 上。黎曼猜想是黎曼在 1859 年提出的。在证明素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。孪生素数猜想1849年，波林那克提出孪生质数猜想（the conjecture of twin primes），即猜测存在无穷多对孪生质数。猜想中的“孪生质数”是指一对质数，它们之间相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孪生质数。费马数被称为“17世纪最伟大的法国数学家”的费马，也研究过质数的性质。他发现，设Fn=2^(2^n)+1，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65,537，都是质数，由于F5太大（F5=4,294,967,297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。这便是费马数。费马死后67年，25岁的瑞士数学家欧拉证明：F5=641×6,700,417是一个合数。以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1,495，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。高斯已经证明，一个正多边形能用直尺和圆规作出当且仅当边数为质数的Fn或若干个为质数的Fn的乘积。梅森素数17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：当2^p-1 中的p是质数时，2^p-1是质数。他验算出：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。 p=2，3，5，7时，2^p-1都是素数，但p=11时，所得2,047=23×89却不是素数。梅森去世250年后，美国数学家科勒证明，2^67-1=193,707,721×761,838,257,287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得杂乱无章，也给人们寻找质数规律造成了困难。目前最大的已知质数是梅森质数2^57,885,161－1。迄今为止，人类仅发现48个梅森质数。由于这种质数珍奇而迷人，它被人们称为“数学珍宝”。中国数学家和语言学家周海中根据已知的梅森质数及其排列，巧妙地运用联系观察法和不完全归纳法，于1992年正式提出了梅森素质分布的猜想(即周氏猜测)。
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。
数论是纯粹数学的分支之一，主要研究整数的性质。而整数的基本元素是素数（也称质数），所以数论的本质是对素数性质的研究。数论被高斯誉为“数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。发现已知的最大素数美国中央密苏里大学数学家柯蒂斯·库珀领导的研究小组通过参加一个名为“互联网梅森素数大索”（GIMPS）的国际合作项目，于日发现了目前已知的最大素数——2^ （即2的次方减1）。该素数是第48个梅森素数，有位；如果用普通字号将它连续打印下来，其长度可超过65公里！美国数学学会发言人迈克·布林宣称：这是数论研究的一项重大突破。质数研究小组在大约1000台大学里的计算机上运行GIMPS的软件，每台计算机都不间断地用了39天时间证明2^是个素数。之后其他研究者也独立验证了这一结果。库珀通过参加GIMPS项目一共发现了3个梅森素数。寻找梅森素数已成为发现已知最大素数的最有效途径。如今世界上有180多个国家和地区近28万人参加了GIMPS项目，并动用超过79万台计算机联网来寻找新的梅森素数。梅森素数是否有无穷多个？这是一个尚未破解的著名数学谜题。证明“弱孪生素数猜想”美国新罕布什尔大学数学家张益唐经过多年努力，在不依赖未经证明推论的前提下，率先证明了一个“弱孪生素数猜想”，即“存在无穷多个之差小于7000万的素数对”。4月17日，他将论文投稿给世界顶级期刊《数学年刊》。美国数学家、审稿人之一亨里克·艾温尼科评价说：“这是一流的数学工作。”他相信不久会有很多人把“7000万”这个数字“变小”。尽管从证明弱孪生素数猜想到证明孪生素数猜想还有相当的距离，英国《自然》杂志在线报道还是称张益唐的证明为一个“重要的里程碑”。由于孪生素数猜想与哥德巴赫猜想密切相关（姐妹问题），很多数学家希望通过解决这个猜想，进而攻克哥德巴赫猜想。值得一提的是，英国数学家戈弗雷·哈代和约翰·李特尔伍德曾提出一个“强孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对，而且还给出其渐近分布形式。中国数学家周海中指出：要证明强孪生素数猜想，人们仍要面对许多巨大的困难。解开“弱哥德巴赫猜想”日，秘鲁数学家哈拉尔德·赫尔弗戈特在巴黎高等师范学院宣称：证明了一个“弱哥德巴赫猜想”，即“任何一个大于7的奇数都能被表示成3个奇素数之和”。他将论文投稿给全球最大的预印本网站（arXiv）；有专家认为这是哥德巴赫猜想研究的一项重大成果。不过，其证明是否成立，还有待进一步考证。赫尔弗戈特在论证技术上主要使用了哈代-李特尔伍德-维诺格拉多夫圆法。在这一圆法中，数学家创建了一个周期函数，其范围包括所有素数。1923年，哈代和李特尔伍德证明，假设广义黎曼猜想成立，三元哥德巴赫猜想对充分大的奇数是正确的；1937年，苏联数学家伊万·维诺格拉多夫更进一步，在无须广义黎曼猜想的情形下，直接证明了充分大的奇数可以表示为3个素数之和。英国数学家安德鲁·格兰维尔称，不幸的是，由于技术原因，赫尔弗戈特的方法很难证明“强哥德巴赫猜想”，即“关于偶数的哥德巴赫猜想”。如今数学界的主流意见认为：要证明强哥德巴赫猜想，还需要新的思路和工具，或者在现有的方法上进行重大的改进。}