关于质数

写了一段寻找质数的Python脚本玩,断断续续跑了两三天,终于把1亿以内的质数全找出来了,并将它们从小到大排列保存为了文本文档,与我一样无聊且又不想自己算的朋友可以右键点击这儿另存为(12.5M)下载下去玩玩。

然后又写了一个脚本统计了一下每n个连续的自然数中质数出现数量的变化,当n=100000时,得到下图:

可以看到,在0~100000间共有9592个质数,在100001~200000间共有8392个质数,…而在 99900001~100000000间则只有5454个质数了,随着数字的增大,质数越来越稀少。

不过,尽管从直观上与经验上可以得出随着数字的增大质数的出现概率越来越小的印象,这个概率却并不会减至0,即不存在最大的质数。关于这个结论,几千年前欧几里德就已经巧妙地证明,他的证明如下:

假设只有有限个质数,如n个:2, 3, 5, …, p,则可以构造一个数M = 2·3·5·…·p + 1。M如果是合数,则必有一个质数因子q,因为只有有限个质数,所以q必然是2, 3, 5, …, p中一个。但是q必然不同于2, 3, 5, …, p中任意一个,因为用2, 3, 5, …, p中的任何一个去除M总是会余1。因此,质数有无穷多个。

质数是有无穷多个的,华裔青年数学家陶哲轩和他的同事则进一步证明了另一个结论:质数存在任意长的等差数列。比如,3, 7, 11三个质数即是一个差为4长度为3的等差数列,陶及他的同事的研究揭示,在质数排列的某个地方,在在一个长度达1001000或其他任意有限值的序列,这些序列的数量是无限的。

上网搜索了一下,目前人类找到的最大的质数似乎是这个:230402457-1,在2005年12月由美国密苏里州立大学的Curtis Cooper和Steven Bonne发现,长度达到惊人的9152052位,是第43个梅森质数(梅森质数指形如 2n-1 的质数,以17世纪法国著名数学家、法兰西科学院奠基人梅森命名),被记作为M30402457,据说这个质数是花了多年时间给700部电脑进行编程之后才被发现。

以下关于梅森质数的描述摘自http://www.mathren.com/n162c12.aspx

梅森素数貌似简单,但研究难度却很大。它不仅需要高深的理论和纯熟的技巧,而且需要进行艰巨的计算。 1772年,被誉为“数学英雄”的欧拉在双目失明的情况下,以惊人的毅力靠心算证明了231-1是第8个梅森素数,该素数有10位数,堪称当时世界上已知的最大素数。1963年9月6日晚上8点,当第23个梅森素数211213-1通过大型计算机发现时,美国广播公司(ABC)中断了正常的节目播放,以第一时间发布了这一重要消息;而发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲,以致于把所有从系里发出的信件都盖上了“211213-1是个素数”的邮戳。特别值得一提的是,中国数学家和语言学家周海中经过多年的研究,于 1992年首先给出了梅森素数分布的准确表达式,为人们探寻梅森素数提供了方便;后来这一成果被国际上命名为“周氏猜测”。

其它:
  除了寻找质数,用计算机来寻找圆周率π也很好玩,非常适合于无聊时用来折腾电脑以及消磨时间。以前我曾在计算机上模拟纸笔运算来计算π,但算法不够好,算得比较慢,而且后来发现当我想算到10亿位或100亿位以上之时,最大的瓶颈居然是我电脑的硬盘空间不够(谁叫我当时那么穷买不起更大的硬盘呢?),毕竟10亿位数字就是1G的空间,除此之外,计算的中间过程也需要很多的硬盘开销。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s