Math 版 (精华区)
发信人: zhchsh (阿胜), 信区: Math
标 题: 【数论的简介】
发信站: 哈工大紫丁香 (2000年10月11日19:37:42 星期三), 站内信件
----------------------------------------------------------------------------
----
数论知识
数论的简介 最大的素数 最完美的数 素数的分类 因数的分解 最大的数表 编程找素数
----------------------------------------------------------------------------
----
【数论的简介】
数论被誉为数学的皇后,他的研究对象是我们大家经常接触的整数的性质,例如求一个数
的最大公约数和最小公倍数,求一个正整数的素因子分解,辗转相除法,求方程的整数解等
等各种问题都是数论要研究的东西. 只有1和数本身作为因数的数叫做素数.例如 2,3,5
,7,3021377等等.素数就像整数世界里的原子,整个整数世界都是由这些原子组成的,比如
15等于3X5,121等于11X11等等.
那么素数到底有多少个呢?早在2000多年前的古希腊,欧几里德就用反证法解决了这个
问题,在他的不朽名著<几何原本>的第四卷命题20中是这样叙述的:"预先给定几个素数,
则有比他们更多的素数."他是这样证明的:设a,b,c是给定的素数,构造一个数:t:t=a*b*
c+1,则已有的素数a,b,c均不能整除t,所以要么t本身就是素数,此时t不等于a,b,c中任意
一个数;要么他能被不同于a,b,c的某个素数整除,因此必然存在一个素数p不同于已有素
数a,b,c.例如:2X3X5+1=31,3X5X7+1=106=2X53.一般地,有了n个素数,就可以构造出n+1个
素数,因此素数有无穷多.
素数的分布也很不均匀,下表是到目前为止所知的小于x的素数的个数pi(x)
x pi(x)
---------------------------- -------------------------
10 4
100 25
1,000 168
10,000 1,229
100,000 9,592
1,000,000 78,498
10,000,000 664,579
100,000,000 5,761,455
1,000,000,000 50,847,534
10,000,000,000 455,052,511
100,000,000,000 4,118,054,813
1,000,000,000,000 37,607,912,018
10,000,000,000,000 346,065,536,839
100,000,000,000,000 3,204,941,750,802
1,000,000,000,000,000 29,844,570,422,669
10,000,000,000,000,000 279,238,341,033,925
100,000,000,000,000,000 2,623,557,157,654,233
1,000,000,000,000,000,000 24,739,954,287,740,860
10,000,000,000,000,000,000 234,057,667,276,344,607
100,000,000,000,000,000,000 2,220,819,602,560,918,840
------------------------------ -----------------------------
不要以为统计这些数据是轻而易举的事,我自己编程序验算到10,000,000,000.用时11小
时45分钟,机器配置是奔腾II266MHz.可想而知,要验算到100,000,000,000,000,000,000
,需要多么大的工作量. 我开始做素数统计工作是很早的事情了,那时,我还没有计算机,
我就利用下班以后的时间在单位的机器上编程序计算,记得到了1987年,我有了一台机器
是Commodore-PC1,CPU是V20 (日本产8088),512KB内存,360KB 5"软驱,让我高兴的是还有
一个30MB的硬盘,这样我就开始了统计工作和造表工作,为了保存数据,我就用360KB的软
盘一张一张地存储.当我统计到10亿以内的素数个数为50847534时,我参考的那本书上记
载的却是50847478!,怎么会多出56个?当时我一味地只是怀疑我的程序有问题,因为以前
曾经出现过错把6869^2和8867^2当成了素数的错误,可是不论我用什么方法进行计算,得
出的结果却总是原来的结果,后来我从另一本书(An Introduction to the history of
mathematics Howard Eves)的Page 435上查出了原因,原来那个错误的数字是一位丹麦数
学家Bertelsen计算的,一些数学书就沿用下来,碰巧我用的就是这样一本书,不过这样我
对我所编的程序更有信心了.现在我有了一台奔腾II,Celeron 333MHz,6.4G硬盘,可以痛
痛快块地大干了.
----------------------------------------------------------------------------
----
【最大的素数】
----------------------------------------------------------------------------
----
26972593-1
这是到目前为止人类所发现的最大素数,它是由纳杨,沃特曼,库洛夫斯基三人在199
9年6月1日发现的,这是一个梅森素数,有2098960位数字,是用Primes95这个软件找到的,
该软件由沃特曼和库洛夫斯基共同编写的,是一个分布在因特网上的应用软件,现在已经
有大约6万人在共同使用这个软件来寻找这种被称为梅森素数的类型的素数.纳扬是这6万
人中之一,在1998年1月28日,美国加利福尼亚大学的大学生克拉克也是利用这个软件发现
了第37个梅森素数,我现在也参加到这个行列中,现在已经检验完三个指数了,结果都不是
素数,每检验一个指数,大约需要60天,当然指数越大时间越长.这个软件的客户端是一个
后台运行的程序,只要你一开机,它就自动运行在后台,对于你的正常工作毫不影响.现在
这个软件已经到了第9版.有兴趣的可以到如下站点去下载:ftp://entropia.com/gimps/
prime95.zip
.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/
primes/
序号 素数 位数 发现人 时间 注释
1 26972593-1 2098960 Nayan, Woltman, Kurowski 1999 Mersenne 38
2 23021377-1 909526 Clarkson, Woltman, Kurowski 1998 Mersenne 37
3 22976221-1 895932 Spence, Woltman 1997 Mersenne 36
4 21398269-1 420921 Armengaud, Woltman 1996 Mersenne 35
5 21257787-1 378632 Slowinski & Gage 1996 Mersenne 34
6 2859433-1 258716 Slowinski & Gage 1994 Mersenne 33
7 2756839-1 227832 Slowinski & Gage 1992 Mersenne 32
8 2216091-1 65050 David Slowinski 1985 Mersenne 31
9 2132049-1 39751 David Slowinski 1983 Mersenne 30
10 2110503-1 33265 Welsh & Colquitt 1988 Mersenne 29
11 286243-1 25962 David Slowinski 1982 Mersenne 28
12 244497-1 13395 Slowinski & Nelson 1979 Mersenne 27
13 223209-1 6987 L. Curt Noll 1979 Mersenne 26
14 221701-1 6533 Nickel & Noll 1978 Mersenne 25
15 219937-1 6002 Bryant Tuckerman 1971 Mersenne 24
16 211213-1 3376 Donald B. Gillies 1963 Mersenne 23
17 29941-1 2993 Donald B. Gillies 1963 Mersenne 22
18 29689-1 2917 Donald B. Gillies 1963 Mersenne 21
19 24423-1 1332 Alexander Hurwitz 1961 Mersenne 20
20 24253-1 1281 Alexander Hurwitz 1961 Mersenne 19
----------------------------------------------------------------------------
----
【最完美的数】
----------------------------------------------------------------------------
----
完美数又称为完全数,最初是由毕达哥拉斯(Pythagoras)的信徒发现的,他们注意到,数6
有一个特性,它等于它自己的因子(不包括它自身)的和:
6=1+2+3,下一个具有同样性质的数是28,28=1+2+4+7+14
接着是496和8128.他们称这类数为完美数.欧几里德在大约公元前350-300年间证明
了:若2^n-1是素数,则数2^(n-1)[2^n-1]是完全数.两千年后,欧拉证明每个偶完全数都具
有这种形式.这就在完全数与梅森数之间建立了紧密的联系,到1998年1月27日为止,共发
现了37个梅森素数,这就是说已发现了37个完全数.
完全数是非常奇特的数,它们有一些特殊性质,例如每个完全数都是三角形数,即都能
写成n(n+1)/2.把它们(6除外)的各位数字相加,直到变成一位数,那么这个一位数一定是
1;它们都是连续奇数的立方和(6除外),除了因子1之外,每个完全数的所有因子(包括自身
)的到数和等于1,比如:
1/2+1/3+1/6=1
完全数都是以6或8结尾的,看看它们的二进制表达式吧:
110
11100
111110000
1111111000000
注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如
果存在的话,将大于10^100.
注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存
在的话,将大于10^100.
完全数Pp ## p Mp的位数 Pp的位数 年代 发现者
6 1 2 1 1 ---- ----
28 2 3 1 2 ---- ----
496 3 5 2 3 ---- ----
8128 4 7 3 4 ---- ----
33550336 5 13 4 8 1456 anonymous
8589869056 6 17 6 10 1588 Cataldi
137438691328 7 19 6 12 1588 Cataldi
2305843008139952128 8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
【素数的分类】
----------------------------------------------------------------------------
----
素数从理论上来说只能分成两类,即偶素数和奇素数,由于历史和人为习惯的原因, 人们
又对素数进行了各种各样的分类,这些分类中最著名的有两种,一种就是前面提到过的梅
森素数,另一种是叫做费马素数.其他的类型的素数不太被人们所熟悉,比如普罗斯素数.
还有另外一种分类法既是按素数本身的形态来区分的,比如说回文素数,下表列出了最近
发现的最大的十个回文素数:
742950290870000078092059247, 742950290871010178092059247,
742950290872020278092059247, 742950290873030378092059247,
742950290874040478092059247, 742950290875050578092059247,
742950290876060678092059247, 742950290877070778092059247,
742950290878080878092059247, 742950290879090978092059247
另一种非常重要的是神秘的素数对,或成为孪生素数,孪生素数是指如果p是素数且p+2也
是素数,则称p和p+2为一对孪生素数,比如5,7;11,13等等.下表是目前所发现的最大的前
二十个孪生素数:
rank prime digits who when comment
1 361700055.239020±1 11755 Henri Lifchitz 1999 Twin
2 835335.239014±1 11751 Ballinger & Gallot 1998 Twin
3 242206083.238880±1 11713 Jarai & Indlekofer 1995 Twin
4 40883037.223456±1 7069 Lifchitz & Gallot 1998 Twin
5 843753.222222±1 6696 Rivera & Gallot 1997 Twin
6 7485.220023±1 6032 Buddenhagen & Gallot 1998 Twin
7 8182815.217838±1 5377 Smith & Gallot 1998 Twin
8 570918348.105120±1 5129 Harvey Dubner 1995 Twin [Ribenboim95, p263]
9 22687485.216557±1 4992 Hanson & Gallot 1999 twin
10 697053813.216352±1 4932 Jarai & Indlekofer 1995 Twin [IJ96]
11 37442007.215440±1 4656 Hanson & Gallot 1999 Twin
12 6797727.215328±1 4622 Tony Forbes 1995 Twin [Forbes97]
13 1692923232.104020±1 4030 Harvey Dubner 1993 Twin [Peterson93]
14 3981.213153±1 3964 Walker & Gallot 1999 Twin
15 245630385.212937±1 3903 Brennen & Gallot 1998 Twin
16 915.211455±1 3452 Ballinger & Gallot 1998 Twin
17 4655478828.103429±1 3439 Harvey Dubner 1993 Twin [IJ96]
18 1706595.211235±1 3389 Brown, Noll, Parady, Smith_G, Smith_J & Zarantonel
lo 1989 Twin [PSZ90]
19 10941.210601±1 3196 Hanson & Gallot 1998 Twin
20 12110457.210006±1 3020 Lifchitz & Gallot 1998 Twin
【因数的分解】
----------------------------------------------------------------------------
----
数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素
数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就
是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几
乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人
吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情
况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研
究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位
数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数
,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个
数是否是素数.
那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所
有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,
比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决
了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对
付这种情况的方法,以下就是这种方法的简单说明:
设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且
v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者 y*y=x*x-n,若能找到两个数x,y满足
前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了20276512
81=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...
这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两
个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在
判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以
2,3,7,8结尾的.
----------------------------------------------------------------------------
----
【最大的数表】
----------------------------------------------------------------------------
----
自然数列:1,2,3,....可以按他们各自的素因子的多少而分成两大类,除1以外,若某
个自然数的素因子只有1和其自身,则称其为素数,否则成为合数.因此,按这种性质,自然
数只有两种状态,要么是素数,要么是合数,如果用0代表素数,用1代表合数,那么整个自然
数列将被替换成:
1,2,3,4,5,6,7,8,9,...
1,0,0,1,0,1,0,1,1,...
将此0,1序列每八位组成一个字节,在限定的范围内,做成一个'素数库',这就是我长
期以来所要完成的目标.
但是,我们看到,以上序列中包含了所有的偶数,我们知道,除了2以外,所有的偶数都
是合数,因此没有必要保存他们,将他们通通都划掉,而且由于2是已经知道的素数,也不必
保存他,则剩下的只是奇数了,显然也包含了所有的奇素数,该数列的通项公式为:
P=2N+1 (N=0,1,2,3,...)
N=(P-1)/2
在这里,P将被称为预选数,其中既有素数,也有合数,N称为数P的序号.现在我们正在
逐步缩小包围圈,从自然数范围缩小到奇数范围,我们还能进一步缩小包围圈吗?答案是肯
定的.为了更好的理解,我们需要引入数论中的一个概念,即剩余类的概念.任给一个自然
数K,则所有自然数除以K所得余数只能是:
0,1,2,3,....K-1
这K种类型,即所有自然数可以分成K类:
KN+0,KN+1,KN+2,...KN+(K-1)
这K种类型的数系被称为数K的剩余系,前面我们已经讨论过的就是2的剩余系:
2N,2N+1
我们保留了其中的一类2N+1,将此数列用0或1按是否素数一一替换,即可做成一个以2为基
的'素数库',要从库中检索某个数是否是素数,只要看看库中的第N位是否是0即可.
要想继续缩小包围圈,大家可以猜到下一步将要划去3的倍数,这样也将6的倍数划去
了,因此我们进一步考虑的是6的剩余系:
6N,6N+1,6N+2,6N+3,6N+4,6N+5
其中只有6N+1,6N+5才包含了大于3的所有素数,其他的4类显然都是合数,我们将6N+1,6N
+5保留下来,并统一成如下的一对公式:
P=3N+5-(N mod 2) (N=0,1,2,3,...)
N=[14P-15-(P mod 6)]/12
利用这一对公式可以造出一个素数库,显然这个库所存储的数只占自然数的三分之一
,这就是以6为基的'素数库'.在进一步将要划去5的倍数,也将2X3X5=30的倍数划去了,因
此下一步是以30为基的'素数库',只剩下如下八种剩余类:
30N+1,30N+7,30N+11,30N+13,30N+17,30N+19,30N+23,30N+29
也可以统一成如下的一对公式:
P=30XINT(N/8)+U(N mod 8) (N=0,1,2,3,....)
N=8XINT(P/30)+V(P mod 30)
其中U(0)=1,U(1)=7,U(2)=11,U(3)=13,U(4)=17,U(5)=19,U(6)=23,U(7)=29
V(1)=0,V(7)=1,V(11)=2,V(13)=3,V(17)=4,V(19)=5,V(23)=6,V(29)=7
用这个公式编制一个'素数库',所保存的数只占自然数的十五分之四,我目前所使用
的就是这个公式,已经做好的最大的素数库有640M字节,他把200亿以下的所有素数全部存
储进去了.下一步将要做一个3200M字节的素数库,这个素数库可以把一千亿以下的所有素
数存储进去.如果继续缩小包围圈,那将是以2X3X5X7=210为基,它将剩下48个有用的剩余
类,所保存的数只占自然数的三十五分之八,再下去就是以 2X3X5X7X11=2310为基,它有4
80个有用的剩余类,一般地,当基B=2X3X5X7...XP 时,有用的剩余类(简化剩余类)实际上
就等于B的欧拉函数的值,所谓的欧拉函数φ(B)是指小于B且与B互素的数的个数.存储效
率即指φ(B)/B,下表所列的就是我所做的素数库的前八个字节的内容:
字节地址 字位序号 0 1 2 3 4 5 6 7 保存的数
0 0 1 7 11 13 17 19 23 29 01H
1 8 31 37 41 43 47 49 53 59 20H
2 16 61 67 71 73 77 79 83 89 10H
3 24 91 97 101 103 107 109 113 119 81H
4 32 121 127 131 133 137 139 143 149 49H
5 40 151 157 161 163 167 169 173 179 24H
6 48 181 187 191 193 197 199 203 209 C2H
7 56 211 217 221 223 227 229 233 239 06H
编程找素数
----------------------------------------------------------------------------
----
编程序来找素数, 有两方面的任务, 一种是判断某数是否是素数, 是则打印出来, 不
是则进一步要求分解出它的因数来; 另一种则是将某一范围内的所有素数全部打印出来
. 为了速度的原因, 一般这些程序都用汇编语言或C语言来编写, 而不能用VISUAL系列的
语言来编写, 我试过VB, 结果速度慢的不可忍受. 在这里为了说明方便, 我都用QB语言
来编写, 因为这是一种编译型语言, 可以将程序编译成EXE 可执行程序. 在过去的386机
时代, 还有一种叫UBASIC的解释型语言, 可以处理极大的整数, 可惜我没找到这种语言
的编译程序, 我这里有这种解释程序和大量的数学源程序, 有兴趣的朋友可以下载回去
试试. 我也编了一个将QB与VB结合起来的程序,速度还可以, 不过需要事先做好素数表,
而且只能处理16位以下的自然数, 范围显然小了一些.所有语言里速度最快的当然要数
汇编语言了, 但是用汇编语言来编数学的应用程序显然非常不方便, 而且源程序也很难
理解. 下面我们就开始来编程序吧.
----------------------------------------------------------------------------
----
问题一. 试将一百万以下的所有素数在屏幕上打印出来并计算总个数. 我们还是从
最简单的方法开始, 用以2 为基的筛法做, (参见最大的数表)
----------------------------------------------------------------------------
----
DEFLNG A-Z
DIM B(0 TO 15) AS INTEGER
FOR I = 0 TO 15
READ B(I)
NEXT
DATA 1,2,4,8,16,32,64,128,256,512
DATA 1024,2048,4096,8192,16384,-32768
AAA:
INPUT "Input a number within 2-1000000:"; N
IF N < 2 OR N > 1000000 THEN
PRINT "Out of range!": GOTO AAA
END IF
K = INT((N - 1) / 32 + 1)
REDIM A(K) AS INTEGER
FOR I = 0 TO K
A(I) = 0
NEXT
A(0) = 1
Q = INT(SQR(N)):Q=INT((Q-(Q MOD 2))/2): H = INT((N - (N MOD 2)) / 2)
FOR I = 1 TO Q
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 2 * I + 1: M = I * (P + 1)
FOR J = M TO H STEP P
R = INT(J / 16): S = B(J MOD 16): A(R) = A(R) OR S
NEXT J
END IF
NEXT I
E = 1
PRINT USING "##########"; 2;
FOR I = 1 TO H
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 2 * I + 1
IF P > N THEN GOTO BBB
E = E + 1
PRINT USING "##########"; P;
END IF
NEXT I
BBB:
PRINT : PRINT "TOTAL:"; E
GOTO AAA
END
----------------------------------------------------------------------------
----
看懂了吧,速度非常快.这个程序分成两部分,第一部分既是执行筛法,第二部分将其打印
出来.下面将编写以6为基的素数表生成器.
----------------------------------------------------------------------------
----
DEFLNG A-Z
DIM B(0 TO 15) AS INTEGER
DIM TM AS STRING
FOR I = 0 TO 15
READ B(I)
NEXT
DATA 1,2,4,8,16,32,64,128,256,512
DATA 1024,2048,4096,8192,16384,-32768
AAA:
INPUT "Input a number within 3-1000000:"; N
IF N < 3 OR N > 1536000 THEN
PRINT "Out of range!": GOTO AAA
END IF
TM = TIME$
K = INT(N / 48 + 1)
REDIM A(K) AS INTEGER
FOR I = 0 TO K
A(I) = 0
NEXT
A(0) = 1
Q = INT(SQR(N))
Q = INT((4 * Q - 3 - (Q MOD 6)) / 12)
H = INT((4 * N - 3 - (N MOD 6)) / 12)
FOR I = 1 TO Q
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 3 * I + 1 + (I MOD 2)
M = INT((4 * P * P - 3 - (P * P MOD 6)) / 12)
U = 3 * I + 4 + ((I + 1) MOD 2)
V = INT((4 * P * U - 3 - ((P * U) MOD 6)) / 12)
W = V - M
FOR J = M TO H STEP 2 * P
R = INT(J / 16): S = B(J MOD 16): A(R) = A(R) OR S
R = INT((J + W) / 16)
IF R <= K THEN
S = B((J + W) MOD 16): A(R) = A(R) OR S
END IF
NEXT J
END IF
NEXT I
E = 2
PRINT USING "##########"; 2; 3;
FOR I = 1 TO H
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 3 * I + 1 + (I MOD 2)
IF P > N THEN GOTO BBB
E = E + 1
PRINT USING "##########"; P;
END IF
NEXT I
BBB:
PRINT : PRINT "TOTAL:"; E
PRINT "START TIME:"; TM
PRINT "END TIME:"; TIME$
GOTO AAA
END
这个程序起码比上边那个快三分之一,程序结构基本相同,但是算法比前一个复杂了一些
----------------------------------------------------------------------------
----------------------------------------------------------------------------
----
数论知识
数论的简介 最大的素数 最完美的数 素数的分类 因数的分解 最大的数表 编程找素数
----------------------------------------------------------------------------
----
【数论的简介】
数论被誉为数学的皇后,他的研究对象是我们大家经常接触的整数的性质,例如求一个数
的最大公约数和最小公倍数,求一个正整数的素因子分解,辗转相除法,求方程的整数解等
等各种问题都是数论要研究的东西. 只有1和数本身作为因数的数叫做素数.例如 2,3,5
,7,3021377等等.素数就像整数世界里的原子,整个整数世界都是由这些原子组成的,比如
15等于3X5,121等于11X11等等.
那么素数到底有多少个呢?早在2000多年前的古希腊,欧几里德就用反证法解决了这个
问题,在他的不朽名著<几何原本>的第四卷命题20中是这样叙述的:"预先给定几个素数,
则有比他们更多的素数."他是这样证明的:设a,b,c是给定的素数,构造一个数:t:t=a*b*
c+1,则已有的素数a,b,c均不能整除t,所以要么t本身就是素数,此时t不等于a,b,c中任意
一个数;要么他能被不同于a,b,c的某个素数整除,因此必然存在一个素数p不同于已有素
数a,b,c.例如:2X3X5+1=31,3X5X7+1=106=2X53.一般地,有了n个素数,就可以构造出n+1个
素数,因此素数有无穷多.
素数的分布也很不均匀,下表是到目前为止所知的小于x的素数的个数pi(x)
x pi(x)
---------------------------- -------------------------
10 4
100 25
1,000 168
10,000 1,229
100,000 9,592
1,000,000 78,498
10,000,000 664,579
100,000,000 5,761,455
1,000,000,000 50,847,534
10,000,000,000 455,052,511
100,000,000,000 4,118,054,813
1,000,000,000,000 37,607,912,018
10,000,000,000,000 346,065,536,839
100,000,000,000,000 3,204,941,750,802
1,000,000,000,000,000 29,844,570,422,669
10,000,000,000,000,000 279,238,341,033,925
100,000,000,000,000,000 2,623,557,157,654,233
1,000,000,000,000,000,000 24,739,954,287,740,860
10,000,000,000,000,000,000 234,057,667,276,344,607
100,000,000,000,000,000,000 2,220,819,602,560,918,840
------------------------------ -----------------------------
不要以为统计这些数据是轻而易举的事,我自己编程序验算到10,000,000,000.用时11小
时45分钟,机器配置是奔腾II266MHz.可想而知,要验算到100,000,000,000,000,000,000
,需要多么大的工作量. 我开始做素数统计工作是很早的事情了,那时,我还没有计算机,
我就利用下班以后的时间在单位的机器上编程序计算,记得到了1987年,我有了一台机器
是Commodore-PC1,CPU是V20 (日本产8088),512KB内存,360KB 5"软驱,让我高兴的是还有
一个30MB的硬盘,这样我就开始了统计工作和造表工作,为了保存数据,我就用360KB的软
盘一张一张地存储.当我统计到10亿以内的素数个数为50847534时,我参考的那本书上记
载的却是50847478!,怎么会多出56个?当时我一味地只是怀疑我的程序有问题,因为以前
曾经出现过错把6869^2和8867^2当成了素数的错误,可是不论我用什么方法进行计算,得
出的结果却总是原来的结果,后来我从另一本书(An Introduction to the history of
mathematics Howard Eves)的Page 435上查出了原因,原来那个错误的数字是一位丹麦数
学家Bertelsen计算的,一些数学书就沿用下来,碰巧我用的就是这样一本书,不过这样我
对我所编的程序更有信心了.现在我有了一台奔腾II,Celeron 333MHz,6.4G硬盘,可以痛
痛快块地大干了.
----------------------------------------------------------------------------
----
【最大的素数】
----------------------------------------------------------------------------
----
26972593-1
这是到目前为止人类所发现的最大素数,它是由纳杨,沃特曼,库洛夫斯基三人在199
9年6月1日发现的,这是一个梅森素数,有2098960位数字,是用Primes95这个软件找到的,
该软件由沃特曼和库洛夫斯基共同编写的,是一个分布在因特网上的应用软件,现在已经
有大约6万人在共同使用这个软件来寻找这种被称为梅森素数的类型的素数.纳扬是这6万
人中之一,在1998年1月28日,美国加利福尼亚大学的大学生克拉克也是利用这个软件发现
了第37个梅森素数,我现在也参加到这个行列中,现在已经检验完三个指数了,结果都不是
素数,每检验一个指数,大约需要60天,当然指数越大时间越长.这个软件的客户端是一个
后台运行的程序,只要你一开机,它就自动运行在后台,对于你的正常工作毫不影响.现在
这个软件已经到了第9版.有兴趣的可以到如下站点去下载:ftp://entropia.com/gimps/
prime95.zip
.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/
primes/
序号 素数 位数 发现人 时间 注释
1 26972593-1 2098960 Nayan, Woltman, Kurowski 1999 Mersenne 38
2 23021377-1 909526 Clarkson, Woltman, Kurowski 1998 Mersenne 37
3 22976221-1 895932 Spence, Woltman 1997 Mersenne 36
4 21398269-1 420921 Armengaud, Woltman 1996 Mersenne 35
5 21257787-1 378632 Slowinski & Gage 1996 Mersenne 34
6 2859433-1 258716 Slowinski & Gage 1994 Mersenne 33
7 2756839-1 227832 Slowinski & Gage 1992 Mersenne 32
8 2216091-1 65050 David Slowinski 1985 Mersenne 31
9 2132049-1 39751 David Slowinski 1983 Mersenne 30
10 2110503-1 33265 Welsh & Colquitt 1988 Mersenne 29
11 286243-1 25962 David Slowinski 1982 Mersenne 28
12 244497-1 13395 Slowinski & Nelson 1979 Mersenne 27
13 223209-1 6987 L. Curt Noll 1979 Mersenne 26
14 221701-1 6533 Nickel & Noll 1978 Mersenne 25
15 219937-1 6002 Bryant Tuckerman 1971 Mersenne 24
16 211213-1 3376 Donald B. Gillies 1963 Mersenne 23
17 29941-1 2993 Donald B. Gillies 1963 Mersenne 22
18 29689-1 2917 Donald B. Gillies 1963 Mersenne 21
19 24423-1 1332 Alexander Hurwitz 1961 Mersenne 20
20 24253-1 1281 Alexander Hurwitz 1961 Mersenne 19
----------------------------------------------------------------------------
----
【最完美的数】
----------------------------------------------------------------------------
----
完美数又称为完全数,最初是由毕达哥拉斯(Pythagoras)的信徒发现的,他们注意到,数6
有一个特性,它等于它自己的因子(不包括它自身)的和:
6=1+2+3,下一个具有同样性质的数是28,28=1+2+4+7+14
接着是496和8128.他们称这类数为完美数.欧几里德在大约公元前350-300年间证明
了:若2^n-1是素数,则数2^(n-1)[2^n-1]是完全数.两千年后,欧拉证明每个偶完全数都具
有这种形式.这就在完全数与梅森数之间建立了紧密的联系,到1998年1月27日为止,共发
现了37个梅森素数,这就是说已发现了37个完全数.
完全数是非常奇特的数,它们有一些特殊性质,例如每个完全数都是三角形数,即都能
写成n(n+1)/2.把它们(6除外)的各位数字相加,直到变成一位数,那么这个一位数一定是
1;它们都是连续奇数的立方和(6除外),除了因子1之外,每个完全数的所有因子(包括自身
)的到数和等于1,比如:
1/2+1/3+1/6=1
完全数都是以6或8结尾的,看看它们的二进制表达式吧:
110
11100
111110000
1111111000000
注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如
果存在的话,将大于10^100.
注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存
在的话,将大于10^100.
完全数Pp ## p Mp的位数 Pp的位数 年代 发现者
6 1 2 1 1 ---- ----
28 2 3 1 2 ---- ----
496 3 5 2 3 ---- ----
8128 4 7 3 4 ---- ----
33550336 5 13 4 8 1456 anonymous
8589869056 6 17 6 10 1588 Cataldi
137438691328 7 19 6 12 1588 Cataldi
2305843008139952128 8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
【素数的分类】
----------------------------------------------------------------------------
----
素数从理论上来说只能分成两类,即偶素数和奇素数,由于历史和人为习惯的原因, 人们
又对素数进行了各种各样的分类,这些分类中最著名的有两种,一种就是前面提到过的梅
森素数,另一种是叫做费马素数.其他的类型的素数不太被人们所熟悉,比如普罗斯素数.
还有另外一种分类法既是按素数本身的形态来区分的,比如说回文素数,下表列出了最近
发现的最大的十个回文素数:
742950290870000078092059247, 742950290871010178092059247,
742950290872020278092059247, 742950290873030378092059247,
742950290874040478092059247, 742950290875050578092059247,
742950290876060678092059247, 742950290877070778092059247,
742950290878080878092059247, 742950290879090978092059247
另一种非常重要的是神秘的素数对,或成为孪生素数,孪生素数是指如果p是素数且p+2也
是素数,则称p和p+2为一对孪生素数,比如5,7;11,13等等.下表是目前所发现的最大的前
二十个孪生素数:
rank prime digits who when comment
1 361700055.239020±1 11755 Henri Lifchitz 1999 Twin
2 835335.239014±1 11751 Ballinger & Gallot 1998 Twin
3 242206083.238880±1 11713 Jarai & Indlekofer 1995 Twin
4 40883037.223456±1 7069 Lifchitz & Gallot 1998 Twin
5 843753.222222±1 6696 Rivera & Gallot 1997 Twin
6 7485.220023±1 6032 Buddenhagen & Gallot 1998 Twin
7 8182815.217838±1 5377 Smith & Gallot 1998 Twin
8 570918348.105120±1 5129 Harvey Dubner 1995 Twin [Ribenboim95, p263]
9 22687485.216557±1 4992 Hanson & Gallot 1999 twin
10 697053813.216352±1 4932 Jarai & Indlekofer 1995 Twin [IJ96]
11 37442007.215440±1 4656 Hanson & Gallot 1999 Twin
12 6797727.215328±1 4622 Tony Forbes 1995 Twin [Forbes97]
13 1692923232.104020±1 4030 Harvey Dubner 1993 Twin [Peterson93]
14 3981.213153±1 3964 Walker & Gallot 1999 Twin
15 245630385.212937±1 3903 Brennen & Gallot 1998 Twin
16 915.211455±1 3452 Ballinger & Gallot 1998 Twin
17 4655478828.103429±1 3439 Harvey Dubner 1993 Twin [IJ96]
18 1706595.211235±1 3389 Brown, Noll, Parady, Smith_G, Smith_J & Zarantonel
lo 1989 Twin [PSZ90]
19 10941.210601±1 3196 Hanson & Gallot 1998 Twin
20 12110457.210006±1 3020 Lifchitz & Gallot 1998 Twin
【因数的分解】
----------------------------------------------------------------------------
----
数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素
数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就
是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几
乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人
吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情
况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研
究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位
数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数
,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个
数是否是素数.
那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所
有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,
比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决
了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对
付这种情况的方法,以下就是这种方法的简单说明:
设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且
v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者 y*y=x*x-n,若能找到两个数x,y满足
前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了20276512
81=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...
这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两
个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在
判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以
2,3,7,8结尾的.
----------------------------------------------------------------------------
----
【最大的数表】
----------------------------------------------------------------------------
----
自然数列:1,2,3,....可以按他们各自的素因子的多少而分成两大类,除1以外,若某
个自然数的素因子只有1和其自身,则称其为素数,否则成为合数.因此,按这种性质,自然
数只有两种状态,要么是素数,要么是合数,如果用0代表素数,用1代表合数,那么整个自然
数列将被替换成:
1,2,3,4,5,6,7,8,9,...
1,0,0,1,0,1,0,1,1,...
将此0,1序列每八位组成一个字节,在限定的范围内,做成一个'素数库',这就是我长
期以来所要完成的目标.
但是,我们看到,以上序列中包含了所有的偶数,我们知道,除了2以外,所有的偶数都
是合数,因此没有必要保存他们,将他们通通都划掉,而且由于2是已经知道的素数,也不必
保存他,则剩下的只是奇数了,显然也包含了所有的奇素数,该数列的通项公式为:
P=2N+1 (N=0,1,2,3,...)
N=(P-1)/2
在这里,P将被称为预选数,其中既有素数,也有合数,N称为数P的序号.现在我们正在
逐步缩小包围圈,从自然数范围缩小到奇数范围,我们还能进一步缩小包围圈吗?答案是肯
定的.为了更好的理解,我们需要引入数论中的一个概念,即剩余类的概念.任给一个自然
数K,则所有自然数除以K所得余数只能是:
0,1,2,3,....K-1
这K种类型,即所有自然数可以分成K类:
KN+0,KN+1,KN+2,...KN+(K-1)
这K种类型的数系被称为数K的剩余系,前面我们已经讨论过的就是2的剩余系:
2N,2N+1
我们保留了其中的一类2N+1,将此数列用0或1按是否素数一一替换,即可做成一个以2为基
的'素数库',要从库中检索某个数是否是素数,只要看看库中的第N位是否是0即可.
要想继续缩小包围圈,大家可以猜到下一步将要划去3的倍数,这样也将6的倍数划去
了,因此我们进一步考虑的是6的剩余系:
6N,6N+1,6N+2,6N+3,6N+4,6N+5
其中只有6N+1,6N+5才包含了大于3的所有素数,其他的4类显然都是合数,我们将6N+1,6N
+5保留下来,并统一成如下的一对公式:
P=3N+5-(N mod 2) (N=0,1,2,3,...)
N=[14P-15-(P mod 6)]/12
利用这一对公式可以造出一个素数库,显然这个库所存储的数只占自然数的三分之一
,这就是以6为基的'素数库'.在进一步将要划去5的倍数,也将2X3X5=30的倍数划去了,因
此下一步是以30为基的'素数库',只剩下如下八种剩余类:
30N+1,30N+7,30N+11,30N+13,30N+17,30N+19,30N+23,30N+29
也可以统一成如下的一对公式:
P=30XINT(N/8)+U(N mod 8) (N=0,1,2,3,....)
N=8XINT(P/30)+V(P mod 30)
其中U(0)=1,U(1)=7,U(2)=11,U(3)=13,U(4)=17,U(5)=19,U(6)=23,U(7)=29
V(1)=0,V(7)=1,V(11)=2,V(13)=3,V(17)=4,V(19)=5,V(23)=6,V(29)=7
用这个公式编制一个'素数库',所保存的数只占自然数的十五分之四,我目前所使用
的就是这个公式,已经做好的最大的素数库有640M字节,他把200亿以下的所有素数全部存
储进去了.下一步将要做一个3200M字节的素数库,这个素数库可以把一千亿以下的所有素
数存储进去.如果继续缩小包围圈,那将是以2X3X5X7=210为基,它将剩下48个有用的剩余
类,所保存的数只占自然数的三十五分之八,再下去就是以 2X3X5X7X11=2310为基,它有4
80个有用的剩余类,一般地,当基B=2X3X5X7...XP 时,有用的剩余类(简化剩余类)实际上
就等于B的欧拉函数的值,所谓的欧拉函数φ(B)是指小于B且与B互素的数的个数.存储效
率即指φ(B)/B,下表所列的就是我所做的素数库的前八个字节的内容:
字节地址 字位序号 0 1 2 3 4 5 6 7 保存的数
0 0 1 7 11 13 17 19 23 29 01H
1 8 31 37 41 43 47 49 53 59 20H
2 16 61 67 71 73 77 79 83 89 10H
3 24 91 97 101 103 107 109 113 119 81H
4 32 121 127 131 133 137 139 143 149 49H
5 40 151 157 161 163 167 169 173 179 24H
6 48 181 187 191 193 197 199 203 209 C2H
7 56 211 217 221 223 227 229 233 239 06H
编程找素数
----------------------------------------------------------------------------
----
编程序来找素数, 有两方面的任务, 一种是判断某数是否是素数, 是则打印出来, 不
是则进一步要求分解出它的因数来; 另一种则是将某一范围内的所有素数全部打印出来
. 为了速度的原因, 一般这些程序都用汇编语言或C语言来编写, 而不能用VISUAL系列的
语言来编写, 我试过VB, 结果速度慢的不可忍受. 在这里为了说明方便, 我都用QB语言
来编写, 因为这是一种编译型语言, 可以将程序编译成EXE 可执行程序. 在过去的386机
时代, 还有一种叫UBASIC的解释型语言, 可以处理极大的整数, 可惜我没找到这种语言
的编译程序, 我这里有这种解释程序和大量的数学源程序, 有兴趣的朋友可以下载回去
试试. 我也编了一个将QB与VB结合起来的程序,速度还可以, 不过需要事先做好素数表,
而且只能处理16位以下的自然数, 范围显然小了一些.所有语言里速度最快的当然要数
汇编语言了, 但是用汇编语言来编数学的应用程序显然非常不方便, 而且源程序也很难
理解. 下面我们就开始来编程序吧.
----------------------------------------------------------------------------
----
问题一. 试将一百万以下的所有素数在屏幕上打印出来并计算总个数. 我们还是从
最简单的方法开始, 用以2 为基的筛法做, (参见最大的数表)
----------------------------------------------------------------------------
----
DEFLNG A-Z
DIM B(0 TO 15) AS INTEGER
FOR I = 0 TO 15
READ B(I)
NEXT
DATA 1,2,4,8,16,32,64,128,256,512
DATA 1024,2048,4096,8192,16384,-32768
AAA:
INPUT "Input a number within 2-1000000:"; N
IF N < 2 OR N > 1000000 THEN
PRINT "Out of range!": GOTO AAA
END IF
K = INT((N - 1) / 32 + 1)
REDIM A(K) AS INTEGER
FOR I = 0 TO K
A(I) = 0
NEXT
A(0) = 1
Q = INT(SQR(N)):Q=INT((Q-(Q MOD 2))/2): H = INT((N - (N MOD 2)) / 2)
FOR I = 1 TO Q
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 2 * I + 1: M = I * (P + 1)
FOR J = M TO H STEP P
R = INT(J / 16): S = B(J MOD 16): A(R) = A(R) OR S
NEXT J
END IF
NEXT I
E = 1
PRINT USING "##########"; 2;
FOR I = 1 TO H
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 2 * I + 1
IF P > N THEN GOTO BBB
E = E + 1
PRINT USING "##########"; P;
END IF
NEXT I
BBB:
PRINT : PRINT "TOTAL:"; E
GOTO AAA
END
----------------------------------------------------------------------------
----
看懂了吧,速度非常快.这个程序分成两部分,第一部分既是执行筛法,第二部分将其打印
出来.下面将编写以6为基的素数表生成器.
----------------------------------------------------------------------------
----
DEFLNG A-Z
DIM B(0 TO 15) AS INTEGER
DIM TM AS STRING
FOR I = 0 TO 15
READ B(I)
NEXT
DATA 1,2,4,8,16,32,64,128,256,512
DATA 1024,2048,4096,8192,16384,-32768
AAA:
INPUT "Input a number within 3-1000000:"; N
IF N < 3 OR N > 1536000 THEN
PRINT "Out of range!": GOTO AAA
END IF
TM = TIME$
K = INT(N / 48 + 1)
REDIM A(K) AS INTEGER
FOR I = 0 TO K
A(I) = 0
NEXT
A(0) = 1
Q = INT(SQR(N))
Q = INT((4 * Q - 3 - (Q MOD 6)) / 12)
H = INT((4 * N - 3 - (N MOD 6)) / 12)
FOR I = 1 TO Q
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 3 * I + 1 + (I MOD 2)
M = INT((4 * P * P - 3 - (P * P MOD 6)) / 12)
U = 3 * I + 4 + ((I + 1) MOD 2)
V = INT((4 * P * U - 3 - ((P * U) MOD 6)) / 12)
W = V - M
FOR J = M TO H STEP 2 * P
R = INT(J / 16): S = B(J MOD 16): A(R) = A(R) OR S
R = INT((J + W) / 16)
IF R <= K THEN
S = B((J + W) MOD 16): A(R) = A(R) OR S
END IF
NEXT J
END IF
NEXT I
E = 2
PRINT USING "##########"; 2; 3;
FOR I = 1 TO H
R = INT(I / 16): S = B(I MOD 16): T = A(R) AND S
IF T = 0 THEN
P = 3 * I + 1 + (I MOD 2)
IF P > N THEN GOTO BBB
E = E + 1
PRINT USING "##########"; P;
END IF
NEXT I
BBB:
PRINT : PRINT "TOTAL:"; E
PRINT "START TIME:"; TM
PRINT "END TIME:"; TIME$
GOTO AAA
END
这个程序起码比上边那个快三分之一,程序结构基本相同,但是算法比前一个复杂了一些
----------------------------------------------------------------------------
----
----
--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.247.254]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：414.036毫秒