神奇的“质数筛”

来源 :初中生学习指导·作文评改版 | 被引量 : 0次 | 上传用户:aa1bb1aa
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
   翻阅日历,品玩数字。灵感,有时就诞生于这无聊,却成就于认真。
  众所周知,一个大于1的整数,如果除了它本身和1以外,不能被其他正整数所整除,这个整数就是质数(也称素数),如2,3,5,7,11等都是质数。在自然数列中,因为限定前提和特征的缘故,质数显得稀少且特别。古往今来,许多数学家都致力于寻找质数,其方法可谓多种多样。
  “埃拉托斯特尼筛”
  公元前3世纪,古希腊学者埃拉托斯特尼提出的著名“筛法”就非常具有代表性。他在一块涂蜡的板上依次写上自然数列的数字,将蜡板固定在一个框上,把其中的1及合数一个个挖去,就得到一个像筛子一样有许多小孔的东西,其中留下的数就是质数,这张数表被称为“埃拉托斯特尼筛”。埃拉托斯特尼是怎样“筛”质数的呢?他的具体做法如下:
  把n个自然数按次序排列起来;
  1不是质数,也不是合数,要划去;
  2是质数,留下来,而把2后面所有2的倍数都划去;
  2后面第一个没划去的数是3,把3留下,再把3后面所有3的倍数都划去;
  3后面第一个没划去的数是5,把5留下,再把5后面所有5的倍数都划去;
  ……
  这样一直做下去,就会把不超过n的全部合数都筛掉,留下的就是不超过n的全部质数。
  例如:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  用“埃拉托斯特尼筛”可以找出不超过30的质数有:2,3,5,7,11,13,17,19,23,29,共10个。
  有人统计过:在1到1000之间,有168个质数;在1000到2000之间,有135个质数;在2000到3000之间,有127个质数;而在3000到4000之间,就只有120个质数了。总之,越往后质数就越稀少。这种方法是世界上最古老的求质数的方法。它原理简单,运用起来很方便。现在,凭借经过改进后的“埃拉托斯特尼筛”,数学家们已经把10亿以内的质数都筛出来了。
  “辛答拉姆筛法”
  4 7 10 13 16 19 …
  7 12 17 22 27 32 …
  10 17 24 31 38 45 …
  13 22 31 40 49 58 …
  16 27 38 49 60 71 …
  ……
  1934年,也就是“埃拉托斯特尼筛”问世两千多年后,一位年轻的印度学生辛答拉姆创造了上表,表中数的排列规律是:第一行(最上层横着数)和第一列(最左边竖着数)的数是相同的,在这一行(列)中,从第二个数起,每一個数与前一个数相差3,例如7-4 = 10-7 = 13-10 = 16-13 = … = 3;在第二行(列)中,从第二个数起,每一个数与前一个数相差5;在第三行(列)中,从第二个数起,每一个数与前一个数相差7;在第四行(列)中,从第二个数起,每一个数与前一个数相差9;在第五行(列)中,从第二个数起,每一个数与前一个数相差11。3,5,7,9,11,13……相信你根据这样的规律也能接着写出第六行、第七行……
  不过,辛答拉姆的发现远比此深刻,并且其数学意义重大。他从中发现并证实了一个极为奇特有趣的现象:在这个表中,随便找一个自然数M,那么2M+1一定不是质数。
  例如:M = 4,2M+1 = 2 × 4+1 = 9,9不是质数;M = 31,2M+1 = 2 × 31+1 = 63,63也不是质数;如此等等。反过来,随便找一个表中没有的自然数M,则2M+1一定是质数。
  例如:M = 11,11不在表中,2M+1 = 2 × 11+1 = 23,23的确是质数; M = 23,23不在表中,2M+1 = 2 × 23+1 = 47,47也是质数;如此等等。
  辛答拉姆猜想:若自然数M出现在这个表中,则2M+1不是质数;若自然数M不出现在这个表中,则2M+1是质数。辛答拉姆极为精彩地证明了这个猜想。
  他写出第n行的第一个数是4+(n-1) × 3 = 3n+1,此行是公差为2n+1的等差数列,所以此行第m列的数是(3n+1)+(m-1)(2n+1) = 2(m+1)n+m;设N是第n行第m列的数,则N = (2m+1)n+m,于是2N+1 = 2[(2m+1)n+m]+1 = 4mn + 2n + 2m + 1 = 2m(2n + 1) + (2n + 1) = (2m+1)(2n+1),显然它是个合数。再设N不在上表中,现在必须2N+1是质数。辛答立姆采用反证法,即证明“若2N+1不是质数,则N必在表中”,这与原命题等价,并且最重要的是证明起来相对要容易得多。事实上,若2N+1不是质数,则有2N + 1 = x·y(x,y为整数),因为2N+1为奇数,则可推知x,y也必为奇数。不妨设x = 2p+1,y =  2q + 1,从而有2N+l = (2p+1)(2q+1),对照上面“N是表中的第n行第m列的数,则2N+1 = (2m+1)(2n+1)”的结论,可确定这里的N表示的是表中第p行第q列的数。由此,人们确信这是寻找质数的又一个独特而有效的方法,它被称为“辛答拉姆筛法”。
  这两种“质数筛”都从一个侧面反映出:研究质数在自然数列中的分布一直是数论最重要和最有吸引力的中心问题之一。
其他文献
有些常用成语字面上有相同语素,词义比较接近,很容易混淆误用,需认真辨析,做到准确理解。  例1:乐于助人是无可厚非的,可是在有的人看来,这是一种迂腐。  “无可厚非”应换成“无可非议’。 “无可厚非”指事情有其一定的道理或原因,语意程度较浅。“无可非议”中的“非议”意为“批评,指责”。 “无可非议”指没有什么可以指责或批评的地方,语意程度较深。  例2:想不到昔日的“浪子”今天却成了英雄,这就不得
期刊
世界上没有两个完全相同的人,却有无数对想要靠近的心。于是,A面和B面的差别滋生出的误会开始和友情拔河,就像顾灵和项笙的故事。  1. A面  项笙不理我了,在这个干净明朗的午后,天空像混搭的果酱般温柔,我正滔滔不绝地说着什么,她突然心事重重地抬起头。  更糟糕的是我丝毫没察觉有什么不妥,还笑着叫了她的外号。她随即跳起来,跑出了美术教室。  艺术楼的走廊空荡荡的,我能听清她离开的脚步声,八、九、十、
期刊
我们常说父爱如山。的确,父亲的爱是深沉的,如大山般高大而庄严。不同于事无巨细、无微不至的母爱,这样的父爱你是否能够理解和接受呢?许多名家在作品中都曾对父爱有过解读,他们记录着自己与父亲的点点滴滴,或感伤流泪,或力量倍增……让我们在这些优秀的作品中,一同读懂“父爱”吧!  莫言:《父亲的严厉》  我父亲今年已经80岁,是村子里最慈祥和善的老人。与我们记忆中的他判若两人。其实,自从有了孙子辈后,他的威
期刊
主持人:“一粥一饭,当思来之不易;半丝半縷,恒念物力维艰。”任何东西,它的到来都不是简单的。对我们中学生而言,生活中要学会理性消费,不大手大脚。请听下面这位同学的演讲。  随着人们经济条件的改善和生活水平的提高,“奢侈消费”的现象普遍出现在人们的日常生活中,甚至许多同学也会购买超出自己支付能力的物品。这些同学可能是为了相互攀比,可能是为了跟风,也可能是的确特别喜欢某种物品。但这种不恰当的消费观念和
期刊
平时,大家习惯于将“俸”和“禄”连用,但在古代,“俸”和“禄”差别相当大。  在《论语别裁》里,南怀瑾曾探讨过“俸”和“禄”的不同,他说:“‘俸’等于现在的月薪,‘禄’有食物配给。禄位是永远的,所以过去重在禄。”如果再细分,“俸”指钱币,又称俸银或俸钱;“禄”指谷物,又称禄米。所以,史料常以俸银和禄米来计算官吏的俸禄。  具体到每个朝代,官员的俸禄发放形式又各有不同。  战国至秦朝,官吏的俸禄以禄
期刊
英文同中文一样,也有很多表示地理方位的词语。但我们在使用英文方位词时却很容易出错。想要用好英文方位词,首先要弄清每个方位词的意思。现在我们就对这些英文方位词一探究竟吧!  ★in, to, on和off在方位名词前的区别  1. in表示A地在B地范围之内。例:Shenyang is in the north of China.  2. to表示A地在B地范圍之外,即二者之间有距离间隔。例:Jap
期刊
电影《银河补习班》是邓超、俞白眉联合执导的一部献礼父亲节的影片,讲述了二十世纪八九十年代一对父子跨越漫长时光收获爱与成长的亲情故事。  剧情简介:浩瀚太空,航天员马飞和顾星河意外失联,遭遇生命最大的危机,此时马飞回忆起自己那个最了不起的爸爸马皓文。马皓文是有名的设计师,设计出了著名的东沛大桥,还被选为了亚运会火炬手,人生非常完美。可是,当在东沛大桥上传递火炬的时候,桥塌了,马皓文担下所有责任在监狱
期刊
提起做家务,同学们会不会觉得既枯燥又烦琐呢?大家在学习之余,有没有帮助父母做家务呢?今天我们来学习做家务时的常用英文表达,希望能够增加大家做家务的乐趣,同时提高英文水平。让我们的身体和嘴巴都动起来吧!  常用词汇  [常用词汇]   [清扫灰尘 clean up 打扫  wipe the table 擦桌子  sweep the floor 扫地;拖地  use the vacuum 使用吸尘器 
期刊
Dolphins live together in groups. These groups are called pods or herds.  A pod has up to 40 dolphins. A herd can have up to several hundred! Beginning at birth, each dolphin depends on other dolphins
期刊
你是一个爱幻想的人吗?你可曾幻想过自己变成大自然中的一棵树、一只小鸟、一片云朵……而成为它们的你,又会经历哪些奇妙的旅程呢?  蝉儿历险记  耿丹慧  我是一只生存艰难的蝉。  经过五年的地下穴居生活之后,一天黄昏,我用锋利发达的前足掘着土,满头大汗,口干舌燥。我心想:唉,这苦日子快要到头了吧。可我又转念一想:反正也已度过五年了,就再忍忍吧,努力拼搏,终究会见到光明!  日复一日,我终于要破土而出
期刊