素数的判断方法研究论文

数学发展史 此书记录了世界初等数学的发展与变迁。可大体分为“数的出现”、“数字与符号的起源与发展”、“分数”、“代数与方程”、“几何”、“数论”与“名著录”七大项，跨度千万年。可让读者了解数学的光辉历史与发展。是将历史与数学结合出的趣味百科读物。数的出现一、数的概念出现 人对于“数”的概念是与身俱来的。从原始人开始，人就能分出一与二与三的区别，从而，就有了对数的认识。而为了表示数，原始人就创造并使用了一种古老却笨拙且不太实用的方法——结绳计数。通过在绳子上打结来表示所指物体的数量，而为了辨认数量，也就出现了数数这一重要的方法。这一方法如今看来十分笨拙，但却是人对数学的认识由零到一的关键一步。从这笨拙的一步人们也意识到：对数学的阐述必须要尽量得简洁清楚。这是一个从那时开始便影响至今的人类第一个数学方面的认识，这也是人类为了解数学而迈出的关键性一步。数字与符号的起源与发展一、数的出现 很快，人类就又迈出了一大步。随着文字的出现，最原始的数字就出现了。且更令人高兴的是，人们将自己的认识代入了设计之中，他们想到了“以一个大的代替多个小的”这种方法来设计，而在字符表示之中，就是“进位制”。在众多的数码之中，有古巴比仑的二十进制数码、古罗马字符，但一直流传至今的，世界通用的阿拉伯数字。它们告诉了我们：简洁的，就是最好的。 而现在，又出现了“二进制数”、“三进制数”等低位进制数，有时人们会认为它们有些过度的“简洁”，使数据会过多得长，而不便书写，且熟悉了十进制的阿拉伯数字后，改变进制的换算也十分麻烦。其实，人是高等动物 ，理解能力强，从古至今都以十为整，所以习惯了十进制。可是，不是所有的东西都有智商，而且不可能智商高到能明显区分1-10，却能通过明显相反的方式表达两个数码。于是，人类创造了“二进制数”，不过它们不便书写，只适用于计算机和某些智能机器。但不可否认的是，它又创造了一种新的数码表示方法。二、符号的出现 加减乘除〈＋、－、×(·)、÷(∶）〉等数学符号是我们每一个人最熟悉的符号，因为不光在数学学习中离不开它们，几乎每天的日常的生活也离不开它们。别看它们这么简单，直到17世纪中叶才全部形成。 法国数学家许凯在1484年写成的《算术三篇》中，使用了一些编写符号，如用D表示加法，用M表示减法。这两个符号最早出现在德国数学家维德曼写的《商业速算法》中，他用“＋”表示超过,用“－”表示不足。1、加号（+）和减号（-） 加减号“＋”，“－”，1489年德国数学家魏德曼在他的著作中首先使用了这两个符号，但正式为大家公认是从1514年荷兰数学家荷伊克开始。到1514年，荷兰的赫克首次用“＋”表示加法，用“－”表示减法。1544年，德国数学家施蒂费尔在《整数算术》中正式用“＋”和“－”表示加减，这两个符号逐渐被公认为真正的算术符号，广泛采用。2、乘号（×、·） 乘号“×”，英国数学家奥屈特于1631年提出用“×”表示相乘。英国数学家奥特雷德于1631年出版的《数学之钥》中引入这种记法。据说是由加法符号＋变动而来，因为乘法运算是从相同数的连加运算发展而来的。另一乘号“·”是数学家赫锐奥特首创的。后来，莱布尼兹认为“×”容易与“X”相混淆，建议用“·”表示乘号，这样，“·”也得到了承认。3、除号（÷） 除法除号“÷”，最初这个符号是作为减号在欧洲大陆流行，奥屈特用“：”表示除或比.也有人用分数线表示比，后来有人把二者结合起来就变成了“÷”。瑞士的数学家拉哈的著作中正式把“÷”作为除号。符号“÷”是英国的瓦里斯最初使用的，后来在英国得到了推广。除的本意是分，符号“÷”的中间的横线把上、下两部分分开，形象地表示了“分”。 至此，四则运算符号齐备了，当时还远未达到被各国普遍采用的程度。4、等号（＝） 等号“＝”，最初是1540年由英国牛津大学教授瑞柯德开始使用。1591年法国数学家韦达在其著作中大量使用后，才逐渐为人们所接受。分数一、分数的产生与定义 人类历史上最早产生的数是自然数（正整数），以后在度量和均分时往往不能正好得到整数的结果，这样就产生了分数。 一个物体，一个图形，一个计量单位，都可看作单位“1”。把单位“1”平均分成几份，表示这样一份或几份的数叫做分数。在分数里，表示把单位“1”平均分成多少份的叫做分母，表示有这样多少份的叫做分子；其中的一份叫做分数单位。 分子,分母同时乘或除以一个相同的数〔0除外〕,分数的大小不变.这就是分数的基本性质.分数一般包括:真分数,假分数,带分数. 真分数小于1. 假分数大于1,或者等于1. 带分数大于1而又是最简分数.带分数是由一个整数和一个真分数组成的。 注意 ：①分母和分子中不能有0，否则无意义。 ②分数中的分子或分母不能出现无理数（如2的平方根），否则就不是分数。 ③一个最简分数的分母中只有2和5两个质因数就能化成有限小数；如果最简分数的分母中只含有2和5以外的质因数那么就能化成纯循环小数；如果最简分数的分母中既含有2或5两个质因数也含有2和5以外的质因数那么就能化成混循环小数。（注：如果不是一个最简分数就要先化成最简分数再判断；分母是2或5的最简分数一定能化成有限小数，分母是其他质数的最简分数一定能化成纯循环小数）二、分数的历史与演变 分数在我们中国很早就有了,最初分数的表现形式跟现在不一样。后来,印度出现了和我国相似的分数表示法。再往后,阿拉伯人发明了分数线,分数的表示法就成为现在这样了。 在历史上，分数几乎与自然数一样古老。早在人类文化发明的初期，由于进行测量和均分的需要，引入并使用了分数。 在许多民族的古代文献中都有关于分数的记载和各种不同的分数制度。早在公元前2100多年，古代巴比伦人（现处伊拉克一带）就使用了分母是60的分数。 公元前1850年左右的埃及算学文献中，也开始使用分数。200多年前，瑞士数学家欧拉，在《通用算术》一书中说，要想把7米长的一根绳子分成三等份是不可能的，因为找不到一个合适的数来表示它．如果我们把它分成三等份，每份是3/7 米．像3/7 就是一种新的数，我们把它叫做分数． 为什么叫它分数呢？分数这个名称直观而生动地表示这种数的特征．例如，一只西瓜四个人平均分，不把它分成相等的四块行吗？从这个例子就可以看出，分数是度量和数学本身的需要——除法运算的需要而产生的． 最早使用分数的国家是中国．我国春秋时代（公元前770年～前476年）的《左传》中，规定了诸侯的都城大小：最大不可超过周文王国都的三分之一，中等的不可超过五分之一，小的不可超过九分之一。秦始皇时代的历法规定：一年的天数为三百六十五又四分之一。这说明：分数在我国很早就出现了，并且用于社会生产和生活。 《九章算术》是我国1800多年前的一本数学专著，其中第一章《方田》里就讲了分数四则算法． 在古代，中国使用分数比其他国家要早出一千多年．所以说中国有着悠久的历史，灿烂的文化 。几何一、公式1、平面图形正方形： S＝a² C＝4a三角形： S＝ah/2 a＝2S/h h＝2S/a平行四边形：S＝ah a＝S/h h＝S/a梯形： S＝(a＋b)h/2 h＝2S/(a＋b) a＝2S/h－b b＝2S/h－a圆形： S＝∏r² C＝2r∏＝∏d r＝d/2＝C/∏/2r²＝S/∏ d＝C/∏半圆： S＝∏r²/2 C＝∏r＋d＝ 顶点数＋面数－块数＝12、立体图形正方体： V＝a³＝S底·a S表＝6a² S底＝a² S侧＝4a² 棱长和＝12a长方体： V＝abh＝S底·h S表＝2(ab＋ac＋bc） S侧＝2(a＋b)h 棱长和＝4(a＋b＋h)圆柱： V＝∏r²h S表＝2∏r²＋∏r²h＝S底（h＋2） S侧＝∏r²h S底＝∏r² 其它柱体：V＝S底h锥体： V＝V柱体/3球： V＝4/3∏r³ S表＝4∏r²顶点数＋面数－棱数＝2数论一、数论概述 人类从学会计数开始就一直和自然数打交道了，后来由于实践的需要，数的概念进一步扩充，自然数被叫做正整数，而把它们的相反数叫做负整数，介于正整数和负整数中间的中性数叫做0。它们合起来叫做整数。（现在，自然数的概念有了改变，包括正整数和0） 对于整数可以施行加、减、乘、除四种运算，叫做四则运算。其中加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行。也就是说，任意两个或两个以上的整数相加、相减、相乘的时候，它们的和、差、积仍然是一个整数。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。 人们在对整数进行运算的应用和研究中，逐步熟悉了整数的特性。比如，整数可分为两大类—奇数和偶数（通常被称为单数、双数）等。利用整数的一些基本性质，可以进一步探索许多有趣和复杂的数学规律，正是这些特性的魅力，吸引了古往今来许多的数学家不断地研究和探索。 数论这门学科最初是从研究整数开始的，所以叫做整数论。后来整数论又进一步发展，就叫做数论了。确切的说，数论就是一门研究整数性质的学科。 二、数论的发展简况 自古以来，数学家对于整数性质的研究一直十分重视，但是直到十九世纪，这些研究成果还只是孤立地记载在各个时期的算术著作中，也就是说还没有形成完整统一的学科。 自我国古代，许多著名的数学著作中都关于数论内容的论述，比如求最大公约数、勾股数组、某些不定方程整数解的问题等等。在国外，古希腊时代的数学家对于数论中一个最基本的问题——整除性问题就有系统的研究，关于质数、和数、约数、倍数等一系列概念也已经被提出来应用了。后来的各个时代的数学家也都对整数性质的研究做出过重大的贡献，使数论的基本理论逐步得到完善。 在整数性质的研究中，人们发现质数是构成正整数的基本“材料”，要深入研究整数的性质就必须研究质数的性质。因此关于质数性质的有关问题，一直受到数学家的关注。 到了十八世纪末，历代数学家积累的关于整数性质零散的知识已经十分丰富了，把它们整理加工成为一门系统的学科的条件已经完全成熟了。德国数学家高斯集中前人的大成，写了一本书叫做《算术探讨》，1800年寄给了法国科学院，但是法国科学院拒绝了高斯的这部杰作，高斯只好在1801年自己发表了这部著作。这部书开始了现代数论的新纪元。 在《算术探讨》中，高斯把过去研究整数性质所用的符号标准化了，把当时现存的定理系统化并进行了推广，把要研究的问题和意志的方法进行了分类，还引进了新的方法。 由于近代计算机科学和应用数学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合论等方面都广泛使用了初等数论范围内的许多研究成果；又文献报道，现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅立叶变换等。此外，数论的许多比较深刻的研究成果也在近似分析、差集合、快速变换等方面得到了应用。特别是现在由于计算机的发展，用离散量的计算去逼近连续量而达到所要求的精度已成为可能。三、数论的分类初等数论 意指使用不超过高中程度的初等代数处理的数论问题，最主要的工具包括整数的整除性与同余。重要的结论包括中国剩余定理、费马小定理、二次互逆律等等。解析数论 借助微积分及复分析的技术来研究关于整数的问题，主要又可以分为积性数论与加性数论两类。积性数论藉由研究积性生成函数的性质来探讨质数分布的问题，其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。加性数论则是研究整数的加法分解之可能性与表示的问题，华林问题是该领域最著名的课题。此外例如筛法、圆法等等都是属于这个范畴的重要议题。我国数学家陈景润在解决“哥德巴赫猜想”问题中使用的是解析数论中的筛法。 代数数论 是把整数的概念推广到代数整数的一个分支。关于代数整数的研究，主要的研究目标是为了更一般地解决不定方程的问题，而为了达到此目的，这个领域与代数几何之间的关联尤其紧密。建立了素整数、可除性等概念。 几何数论是由德国数学家、物理学家闵可夫斯基等人开创和奠基的。主要在于透过几何观点研究整数（在此即格子点）的分布情形。几何数论研究的基本对象是“空间格网”。在给定的直角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对几何学和结晶学有着重大的意义。最著名的定理为Minkowski 定理。由于几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。 计算数论 借助电脑的算法帮助数论的问题，例如素数测试和因数分解等和密码学息息相关的话题。 超越数论 研究数的超越性，其中对于欧拉常数与特定的 Zeta 函数值之研究尤其令人感到兴趣。 组合数论 利用组合和机率的技巧，非构造性地证明某些无法用初等方式处理的复杂结论。这是由艾狄胥开创的思路。四、皇冠上的明珠 数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。 简要列出几颗“明珠”：费尔马大定理、孪生素数问题、歌德巴赫猜想、角谷猜想、圆内整点问题、完全数问题…… 五、中国人的成绩 在我国近代，数论也是发展最早的数学分支之一。从二十世纪三十年代开始，在解析数论、刁藩都方程、一致分布等方面都有过重要的贡献，出现了华罗庚、闵嗣鹤、柯召等第一流的数论专家。其中华罗庚教授在三角和估值、堆砌素数论方面的研究是享有盛名的。1949年以后，数论的研究的得到了更大的发展。特别是在“筛法”和“歌德巴赫猜想”方面的研究，已取得世界领先的优秀成绩。 特别是陈景润在1966年证明“歌德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”以后，在国际数学引起了强烈的反响，盛赞陈景润的论文是解析数学的名作，是筛法的光辉顶点。至今，这仍是“歌德巴赫猜想”的最好结果。名著录《几何原本》 欧几里得 约公元前300年 《周髀算经》 作者不详 时间早于公元前一世纪 《九章算术》 作者不详 约公元一世纪 《孙子算经》 作者不详 南北朝时期 《几何学》 笛卡儿 1637年 《自然哲学之数学原理》 牛顿 1687年 《无穷分析引论》 欧拉 1748年 《微分学》 欧拉 1755年 《积分学》（共三卷） 欧拉 1768－1770年 《算术探究》 高斯 1801年 《堆垒素数论》 华罗庚 1940年左右 任意选一段吧!!!

质数(又称为素数） 1.就是在所有比1大的整数中，除了1和它本身以外，不再有别的因数，这种整数叫做质数。还可以说成质数只有1和它本身两个约数。2.素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任 何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数； 又如，12 ＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以 外，不能表示为其它任何两个整数的乘积，所以13是一个素数。质数的概念 一个数，如果只有1和它本身两个因数，这样的数叫做质数（或素数）。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数或合数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。（1不是质数，也不是合数）著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。质数中除2是偶数外，其他都是奇数。质数表上的质数 现在，数学家找到的最大的梅森数是一个有9808357位的数：2^32582657-1。数学虽然可以找到很大的质数，但质数的规律还是无法循通。

现在，确定性素数判定法已经有很多种，常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同，威廉斯方法比较适合10^20到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数，对于32位机器数，由于都小于10^10，所以一般都用试除法来判定。阿格拉瓦法虽然是log(n)的多项式级算法，但目前只有理论上的意义，根本无法实用，因为它的时间复杂度是O(log(n)^12)，这个多项式的次数太高了。就拿最慢的试除法跟它来比吧，试除法的时间复杂度为O(n^(1/2)*log(n)^2)，当n = 16时，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要让两者速度相当，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^，此时需要进行的运算次数为log(n)^12 = 10^（注意：本文中log（）函数缺省以2为底），这样的运算次数在一台主频3GHz的计算机上运行也要10^年才能运行完，除了这些确定性素数判定法外，还有基于概率的非确定性素数判定法，最常用的就是米勒-拉宾法。

算好,我以前也研究过素数问题.现在资料还保存着.. 拿来给你分享吧. (这个算法检测速度,还是很快的,你可以试试看哦~~)一种适合32位机器数的确定性素数判定法作者：王浩（）此论文是为发布个人研究成果与大家分享交流而提交，本人教育背景如下：计算机应用专业/管理工程专业双学士天津大学于1995年到1999年在校就读日期________________2006-11-28___________________ 摘要一种适合32位机器数的确定性素数判定法作者：王浩本文通过对米勒-拉宾非确定性素数判定法如何转化为确定性素数判定法的研究，发现了与之相关的伪素数的一些性质，引入了伪素数的最小可判定底数的概念，并总结出了一些规律。通过这些规律找出了一种特别适合32位机器数的确定性素数判定法，该方法对于32位机器数进行素数判定最多只需要进行16log(n) 次乘/除法。该方法具有实现简单、速度快的优点，非常具有推广价值。本文中总结出的一些规律如果能够得到证明和推广，则有可能彻底解决把米勒-拉宾非确定性素数判定法转化为确定性素数判定法的问题，从而对素数判定理论和实践产生一定的促进作用。本文共有五章。分述如下：第一章：讲述素数判定法的现状，列举了目前常用的一些素数判定法及其适用范围。第二章：讲解伪素数表生成过程。第三章：分析伪素数表，引入了伪素数的最小可判定底数的概念，并且总结出了一些规律。根据这些规律，找出了一种特别适合32位机器数的确定性素数判定法，并且进行了多种优化，给出了时间复杂度分析。第四章：算法的C++语言实现和解释说明。第五章：算法的可推广性分析和未来发展展望。目录第一章 素数判定法现状... 1第二章 2-伪素数表的生成... 2第三章 寻找2-伪素数的最小可判定底数... 3第四章 算法实现和解释... 5第五章 算法可推广性分析... 8参考文献... 9词汇表素数判定法：判定一个自然数是否素数的方法。确定性素数判定法：一个素数判定法判定某个自然数为素数的充要条件是该自然数确实是素数，该判定法就是确定性素数判定法。即该判定法不存在误判的可能性。32位机器数：在计算机上用32个二进制位表示的无符号整数。64位机器数：在计算机上用64个二进制位表示的无符号整数。第一章 素数判定法现状现在，确定性素数判定法已经有很多种，常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同，威廉斯方法比较适合10^20到10^50之间的数，艾德利曼和鲁梅利法适合大于10^50的数，对于32位机器数，由于都小于10^10，所以一般都用试除法来判定。也许有人会问：“你为什么没有提马宁德拉.阿格拉瓦法呢？不是有人说它是目前最快的素数判定法吗？” 其实这是一个很大的误解，阿格拉瓦法虽然是log(n)的多项式级算法，但目前只有理论上的意义，根本无法实用，因为它的时间复杂度是O(log(n)^12)，这个多项式的次数太高了。就拿最慢的试除法跟它来比吧，试除法的时间复杂度为O(n^(1/2)*log(n)^2)，当n = 16时，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要让两者速度相当，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^，此时需要进行的运算次数为log(n)^12 = 10^（注意：本文中log（）函数缺省以2为底），这样的运算次数在一台主频3GHz的计算机上运行也要10^年才能运行完，看来我们这辈子是别指望看到阿格拉瓦法比试除法快的这一天啦！除了这些确定性素数判定法外，还有基于概率的非确定性素数判定法，最常用的就是米勒-拉宾法。对于32位机器数（四则运算均为常数时间完成），试除法的时间复杂度是O(n^(1/2))，而米勒-拉宾法的时间复杂度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉宾法的非确定性，往往我们在需要确定解时仍然要依靠速度较慢的试除法。那是否可以通过扩展米勒-拉宾法，来找到一种更快的确定性素数判定法呢？结论是肯定的，本文就带你一起寻找这样一种方法。第二章 2-伪素数表的生成既然要扩展米勒-拉宾法，那首先我们应该知道为什么米勒-拉宾法是个非确定性素数判定法？答案很简单，由于伪素数的存在。由于米勒-拉宾法使用费尔马小定理的逆命题进行判断，而该逆命题对极少数合数并不成立，从而产生误判，这些使费尔马小定理的逆命题不成立的合数就是伪素数。为了研究伪素数，我们首先需要生成伪素数表，原理很简单，就是先用筛法得出一定范围内的所有素数，然后逐一判定该范围内所有合数是否使以2为底数的费尔马小定理的逆命题不成立，从而得出该范围内的2-伪素数表。我的程序运行了100分钟，得出了32位机器数范围内的2-伪素数表，如下：345204724652701.........42868486942894700214289641621428988420142899060894293088801429332904142948685094294901761（共10403个，由于篇幅所限，中间部分省略。）第三章 寻找2-伪素数的最小可判定底数对于2-伪素数表的每一个伪素数，寻找最小的可以判定它们是合数的底数，我把这个底数称之为最小可判定底数。特别地，对于绝对伪素数，它的最小质因子即是它的最小可判定底数。由于已经证明了绝对伪素数至少有三个质因子，所以这个最小质因子一定不大于n^(1/3)。下面就是我找到的最小可判定底数列表：341 3561 3645 31105 51387 31729 71905 32047 32465 52701 5.........4286813749 34288664869 34289470021 54289641621 34289884201 34289906089 34293088801 34293329041 34294868509 74294901761 3通过统计这个列表，我发现了一个规律，那就是所有的最小可判定底数都不大于n^(1/3)，由前述可知，对于绝对伪素数，这个结论显然成立。而对于非绝对伪素数，虽然直观上觉得它应该比绝对伪素数好判定出来，但是我无法证明出它的最小可判定底数都不大于n^(1/3)。不过没关系，这个问题就作为一个猜想留给数学家来解决吧，更重要的是我已经通过实验证明了在32位机器数范围内这个结论成立。我们还有没有更好的方法来进一步减小最小可判定底数的范围呢？有的！我们可以在计算平方数时进行二次检测，下面是进行了二次检测后重新计算的最小可判定底数列表：341 2561 2645 21105 21387 21729 21905 22047 32465 22701 2.........4286813749 24288664869 24289470021 24289641621 24289884201 24289906089 24293088801 24293329041 24294868509 24294901761 3很显然，二次检测是有效果的，经过统计，我发现了新的规律，那就是经过二次检测后所有的最小可判定底数都不大于n^(1/6)，真的是开了一个平方呀，哈哈！这个结论的数学证明仍然作为一个猜想留给数学家们吧。我把这两个猜想叫做费尔马小定理可判定上界猜想。而我已经完成了对32位机器数范围内的证明。通过上面总结的规律，我们已经可以设计出一个对32位机器数进行素数判定的 O(n^(1/6)*log(n)) 的确定性方法。但是这还不够，我们还可以优化，因为此时的最小可判定底数列表去重后只剩下了5个数（都是素数）：{2,3,5,7,11}。天哪，就是前5个素数，这也太容易记忆了吧。不过在实现算法时，需要注意这些结论都是在2-伪素数表基础上得来的，也就是说不管如何对2的判定步骤必不可少，即使当2>n^(1/6)时。还有一些优化可以使用，经过实验，当n>=7^6时，可以不进行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正确的。这样就可以把判定次数降为4次以下，而每次判定只需要进行4log(n)次乘除法（把取余运算也看作除法），所以总的计算次数不会超过16log(n)。经过实验，最大的计算次数在n=4294967291时出现，为496次。第四章 算法实现和解释算法实现如下：（使用C++语言）#include #include <>using namespace std;//定义跨平台的64位机器数类型#ifndef _WIN32typedef unsigned long long longlong_t;#elsetypedef unsigned __int64 longlong_t;#endif//使用费尔马小定理和二次检测针对一个底数进行判定bool IsLikePrime(longlong_t n, longlong_t base){ longlong_t power = n-1; longlong_t result = 1; longlong_t x = result; longlong_t bits = 0; longlong_t power1 = power; //统计二进制位数 while (power1 > 0) { power1 >>= 1; bits++; } //从高位到低位依次处理power的二进制位 while(bits > 0) { bits--; result = (x*x)%n; //二次检测 if (result == 1 && x != 1 && x != n-1) { return false; } if ((power&((longlong_t)1<= primes_six[3]); for (int i = 0; i < num; i++) { if (bIsLarge) { //当n >= 7^6时，不进行上界判断，固定地用{2,5,7,11}做判定。 if (primes[i] == 3) continue; } else { //当n < 7^6时，进行上界判断，但是2例外。 if (primes[i] != 2 && n < primes_six[i]) break; } //做一次子判定 if (!IsLikePrime(n, primes[i])) return false; } //所有子判定通过，则n必为素数！ return true;}//主程序int main(){ longlong_t n; //对标准输入的每一个数进行素数判定 while (cin >> n) { if (JudgePrime(n)) { //如果是素数，则输出到标准输出。 cout << n << endl; } //如果是合数，不输出。 } return 0;}程序中已经加了足够的注释，应该不难理解。需要说明的一点是，虽然我在输入时使用了longlong_t，那是为了类型一致性，有效的输入范围仍然是0 ~ 2^32-1 。第五章 算法可推广性分析如果前述的费尔马小定理可判定上界猜想可以被证明，那么该算法可以被推广到任意位数的n，此时的时间复杂度为O(n^(1/6)*log(n)^3)。这样我们就可以完成米勒-拉宾非确定性素数判定法向确定性素数判定法的转化，这对于数论理论是一个补充，对于实践中使用米勒-拉宾素数判定法具有指导意义。本文所做的研究只是向米勒-拉宾非确定性素数判定法的确定化方向迈出了一小步，我相信，在不久的将来，米勒-拉宾非确定性素数判定法的确定化方向会有更大进展，从而对数论理论和实践产生深远影响。参考文献《计算机算法设计与分析（第2版）》，王晓东编著，电子工业出版社，2004年7月。

//谭浩强C语言一书中的算法，我替你稍微润色了一下#include <>#include using namespace std;int _tmain(int argc, _TCHAR* argv[]){ do { cout << "|---------------------------|" << endl; cout << "|0.退出 |" << endl; cout << "|1.继续 |" << endl; cout << "|---------------------------|" << endl; int m; cin >> m; if (m == 0) { break; } else if (m == 1) { cout << "请输入一个整数:"; cin >> m; int k = sqrt((double)m); int i = 2; for (i = 2; i <= k; i++) { if (m%i == 0) break; } if (i > k) cout << m << "是一个素数" << endl; else cout << m << "不是一个素数" << endl; } else continue; } while(true); }///////////////////////////////////////////////////////////// 如果你真的对这个又兴趣，你可以参加“因特网梅森素数大搜索”(GIMPS)活动！现在人们查找到的最大素数也才700位，据《新科学家》杂志网站1日报道，这位名叫约翰·芬德力的数学爱好者五年前用自己的家用台式电脑加入了 “因特网梅森素数大搜索”(GIMPS)活动，他也是用这台普通的台式机偶然间发现这个素数的。在5月30日正式向外界公布这一消息之前，他还花费了两周的时间进行验证。而另外两位身在法国和加拿大的“因特网梅森素数大搜索”活动的志愿者也证实了芬德力的发现。而就在半年前，美国的一位学生曾发现第40个梅森素数，它共有6320430位数。1995年，美国程序设计师乔治·沃特曼整理有关梅森素数的资料，编制了一个梅森素数计算程序，并将其放置在因特网上供数学爱好者使用，这就是 “因特网梅森素数大搜索”计划。目前有6万多名志愿者、超过20万台计算机参与这项计划。该计划采取分布式计算方式，利用大量普通计算机的闲置时间，获得相当于超级计算机的运算能力，第37、38和39个梅森素数(梅森素数是指能被2的n次方减一的素数)都是用这种方法找到的。美国一家基金会还专门设立了 10万美元的奖金，鼓励第一个找到超过千万位素数的人。

楼上的那个论文看着真太深奥了。下面是我用的笨方法如果一个数A等于其它两个数M和N的乘积（1和本身除外），则M和N之中（除非M=N），必然有一个小于A的二次方根，另一个大于A的二次方根。计算出A的二次方根，再找出小于A的二次方根的所有素数。用A分别除这些素数，如果均不能整除，则A就是素数。

感悟数学 曾听一位奥数老师说过这么一句话：学数学，就犹如鱼与网；会解一道题，就犹如捕捉到了一条鱼，掌握了一种解题方法，就犹如拥有了一张网；所以，“学数学”与“学好数学”的区别就在与你是拥有了一条鱼，还是拥有了一张网。 数学，是一门非常讲究思考的课程，逻辑性很强，所以，总会让人产生错觉。 数学中的几何图形是很有趣的，每一个图形都互相依存，但也各有千秋。例如圆。计算圆的面积的公式是S=∏r²，因为半径不同，所以我们经常会犯一些错。例如，“一个半径为9厘米和一个半径为6厘米的比萨饼等于一个半径为15厘米的比萨饼”，在命题上，这道题目先迷惑大家，让人产生错觉，巧妙地运用了圆的面积公式，让人产生了一个错误的天平。 其实，半径为9厘米和一个半径为6厘米的比萨饼并不等于一个半径为15厘米的比萨饼，因为半径为9厘米和一个半径为6厘米的比萨饼的面积是S=∏r²=9²∏+6²∏=117∏，而半径为15厘米的比萨饼的面积是S=∏r²=15²∏=225∏，所以，半径为9厘米和一个半径为6厘米的比萨饼是不等于一个半径为15厘米的比萨饼的。 数学，就像一座高峰，直插云霄，刚刚开始攀登时，感觉很轻松，但我们爬得越高，山峰就变得越陡，让人感到恐惧，这时候，只有真正喜爱数学的人才会有勇气继续攀登下去，所以，站在数学的高峰上的人，都是发自内心喜欢数学的。 记住，站在峰脚的人是望不到峰顶的。数学小论文 关于“0” 0，可以说是人类最早接触的数了。我们祖先开始只认识没有和有，其中的没有便是0了，那么0是不是没有呢？记得小学里老师曾经说过“任何数减去它本身即等于0，0就表示没有数量。”这样说显然是不正确的。我们都知道，温度计上的0摄氏度表示水的冰点（即一个标准大气压下的冰水混合物的温度），其中的0便是水的固态和液态的区分点。而且在汉字里，0作为零表示的意思就更多了，如：1）零碎；小数目的。2）不够一定单位的数量……至此，我们知道了“没有数量是0，但0不仅仅表示没有数量，还表示固态和液态水的区分点等等。” “任何数除以0即为没有意义。”这是小学至中学老师仍在说的一句关于0的“定论”，当时的除法（小学时）就是将一份分成若干份，求每份有多少。一个整体无法分成0份，即“没有意义”。后来我才了解到a/0中的0可以表示以零为极限的变量（一个变量在变化过程中其绝对值永远小于任意小的已定正数），应等于无穷大（一个变量在变化过程中其绝对值永远大于任意大的已定正数）。从中得到关于0的又一个定理“以零为极限的变量，叫做无穷小”。 “105、203房间、2003年”中，虽都有0的出现，粗“看”差不多；彼此意思却不同。105、2003年中的0指数的空位，不可删去。203房间中的0是分隔“楼（2）”与“房门号（3）”的（即表示二楼八号房），可删去。0还表示…… 爱因斯坦曾说：“要探究一个人或者一切生物存在的意义和目的，宏观上看来，我始终认为是荒唐的。”我想研究一切“存在”的数字，不如先了解0这个“不存在”的数，不至于成为爱因斯坦说的“荒唐”的人。作为一个中学生，我的能力毕竟是有限的，对0的认识还不够透彻，今后望（包括行动）能在“知识的海洋”中发现“我的新大陆”。

素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任 何其它两个整数的乘积。