大学数学实验报告----素数

数学实验报告

实验五素数

学院：数学与信息科学学院

班级：09级数学（4）班

姓名：***

学号：***

实验五素数实验

名称

素数

实验目的掌握素数的含义及其性质,并能熟练的运用素数的判别与求解、生成素数的公式、素数的分布；学会探讨素数的规律及其相关的某些有趣的问题,同时掌握一些基本的、常用的方法。

实验

环境

Mathematica4.0系统

实验的基本理论与方法1、用Eratosthenes筛法和试除法求解小于等于n的素数；

2、Fermat判别法和Mersenne数判别是否为素数；

3、生成素数的公式有n2+n+41,n2-79n+1601,6n2+6n+31；

4、素数的分布：利用程序求解某一区间内素数的个数。

实验的内容与步骤一、素数的产生、求解及判别

1、素数的产生程序

Table Prime n,n,25

运行结果

2、素数的求解

利用Eratosthenes 筛选法,通过计算机编程求1000以内的所有素数

输入程序：.

Sieve n_Integer:

Module t,i,temp,

For i2,i n,i,AppendTo t,i;

For i1,Prime i Sqrt n,i,temp Prime i;

t Select t,#1temp Mod#1,temp0&;t Sieve1000

运行结果：

（2）用试除法求所有小于等于1000的素数

输入程序：

DivPrime n_Integer:

Module t,i,j,temp,divided,

For i2,i n,i,j1;divided False;

While Prime j Sqrt i&÷d,

temp Prime j;

divided Mod i,temp0;j j1;

If divided,AppendTo t,i;t

DivPrime1000

运行结果：

（3）判断Eratosthenes 筛选法与试除法哪个更有效？取n=1000时，程序如下

Sieve n_Integer:

Module

t,i,temp,

For i2,i n,i,AppendTo t,i;

For i1,Prime i Sqrt n,i,temp Prime i;

t Select t,#1temp Mod#1,temp0&; Timing Sieve1000

S i e v e n_I n t e g e r:

M o d u l e

t,i,t e m p,

F o r i2,i n,i,A p p e n d T o t,i;

F o r i1,P r i m e i S q r t n,i,t e m p P r i m e i;

t S e l e c t t,#1t e m p M o d#1,t e m p0&; T i m i n g S i e v e1000

0.031Null Second,Null2

DivPrime n_Integer:

Module

t,i,j,temp,divided,

For i2,i n,i,

j1;divided False;

While Prime j Sqrt i&÷d,

temp Prime j;

divided Mod i,temp0;j j1;

If divided,AppendTo t,i;

Timing DivPrime1000

D i v P r i m e n_I n t e g e r:

M o d u l e

t,i,j,t e m p,d i v i d e d,

F o r i2,i n,i,

j1;d i v i d e d F a l s e;

W h i l e P r i m e j S q r t i&&d i v i d e d,

t e m p P r i m e j;

d i v i d

e d M o d i,t e m p0;j j1;

I f d i v i d e d,A p p e n d T o t,i;

T i m i n g D i v P r i m e1000

0.156Null Second,Null2

Sieve n_Integer:

Module

t,i,temp,

For i2,i n,i,AppendTo t,i;

For i1,Prime i Sqrt n,i,temp Prime i;

t Select t,#1temp Mod#1,temp0&; Timing Sieve10000

S i e v e n_I n t e g e r:

M o d u l e

t,i,t e m p,

F o r i2,i n,i,A p p e n d T o t,i;

F o r i1,P r i m e i S q r t n,i,t e m p P r i m e i;

t S e l e c t t,#1t e m p M o d#1,t e m p0&; T i m i n g S i e v e10000

2.11Null Second,Null2

D i v P r i m e n_I n t e g e r:

M o d u l e

t,i,j,t e m p,d i v i d e d,

F o r i2,i n,i,

j1;d i v i d e d F a l s e;

W h i l e P r i m e j S q r t i&&d i v i d e d,

t e m p P r i m e j;

d i v i d

e d M o d i,t e m p0;j j1;

I f d i v i d e d,A p p e n d T o t,i;

T i m i n g D i v P r i m e10000

D i v P r i m e n_I n t e g e r:

M o d u l e

t,i,j,t e m p,d i v i d e d,

F o r i2,i n,i,

j1;d i v i d e d F a l s e;

W h i l e P r i m e j S q r t i&&d i v i d e d,

t e m p P r i m e j;

d i v i d

e d M o d i,t e m p0;j j1;

I f d i v i d e d,A p p e n d T o t,i;

T i m i n g D i v P r i m e10000

2.Null Second,Null2

M n_I n t e g e r:M o d u l e y,k,m2;k m^n1;

x M o d k,n;

P r i n t n,"",P r i m e Q n,"",x,"",G C D m,n D o M n,n,2,100

M n_I n t e g e r:M o d u l e y,k,m2;k m^n1;

x M o d k,n;

P r i n t n,"",P r i m e Q n,"",x,"",G C D m,n D o M n,n,2,100

13True11 14False22 15False41 16False02 17True11 18False142 19True11 20False82 21False41 22False22 23True11 24False82 25False161 26False22 27False131 28False82 29True11 30False22 31True11 32False02 33False41 34False22 35False91 36False322 37True11 38False22 39False41 40False82 41True11 42False322 43True11 44False82 45False311 46False22 47True11 48False322 49False151 50False122 51False41 52False82 53True11 54False142 55False491

57False41 58False22 59True11 60False82 61True11 62False22 63False41 64False02 65False161 66False322 67True11 68False82 69False41 70False222 71True11 72False322 73True11 74False22 75False341 76False82 77False91 78False322 79True11 80False482 81False401 82False22 83True11 84False322 85False161 86False22 87False41 88False402 89True11 90False322 91False641 92False82 93False41 94False22 95False541 96False322 97True11 98False582 99False581

M n_Integer:Module y,k,m3;k m^n1;

x Mod k,n;

Print n,"",PrimeQ n,"",GCD m,n,"",x Do M n,n,2,100

M n_I n t e g e r:M o d u l e y,k,m3;k m^n1;

x M o d k,n;

P r i n t n,"",P r i m e Q n,"",G C D m,n,"",x D o M n,n,2,100

27False30 28False127 29True11 30False33 31True11 32False111 33False39 34False13 35False14 36False327 37True11 38False13 39False39 40False127 41True11 42False333 43True11 44False127 45False336 46False13 47True11 48False327 49False143 50False133 51False39 52False127 53True11 54False327 55False14 56False13 57False39 58False13 59True11 60False327 61True11 62False13 63False39 64False143 65False116 66False345 67True11 68False127 69False39

71True11

72False327

73True11

74False13

75False369

76False127

77False125

78False39

79True11

80False127

81False30

82False13

83True11

84False375

85False181

86False13

87False39

88False175

89True11

90False363

91False11

92False127

93False39

94False13

95False124

96False375

97True11

98False159

99False327

100False167

Null2

m=4时

输入程序：

M n_Integer:Module y,k,m4;k m^n1;

x Mod k,n;

Print n,"",PrimeQ n,"",GCD m,n,"",x Do M n,n,2,100

运行结果：

M n_Integer:Module y,k,m4;k m^n1;

x Mod k,n;

Print n,"",PrimeQ n,"",GCD m,n,"",x Do M n,n,2,100

2True20

3True11

4False40

5True11

6False24

7True11

8False40

9False17

10False24

11True11

12False44

13True11

14False24

15False11

16False40

17True11

18False216

19True11

20False44

21False116

22False24

23True11

24False416

25False16

26False24

27False17

28False48

29True11

30False24

31True11

32False40

33False116

34False24

35False111

36False416

37True11

38False24

39False116

40False424

41True11 42False216 43True11 44False420 45False116 46False24 47True11 48False416 49False129 50False244 51False116 52False412 53True11 54False234 55False136 56False432 57False116 58False24 59True11 60False44 61True11 62False24 63False116 64False40 65False161 66False234 67True11 68False464 69False116 70False264 71True11 72False416 73True11 74False24 75False131 76False464 77False14 78False210 79True11 80False464 81False161 82False24 83True11 84False416

85False11

86False24

87False116

88False416

89True11

90False234

91False11

92False464

93False116

94False24

95False166

96False464

97True11

98False232

99False197

100False444

（2）对n=2,3,..,300,判断哪些Mersenne数Mn=2n-1是素数？输入程序：

t1;F o r n2,n100,n,

P r i n t n,"",P r i n t Q n,"",2^n1,

F a c t o r I n t e g e r2^n1

运行结果：

t1;F o r n2,n100,n,

P r i n t n,"",P r i n t Q n,"",2^n1,

F a c t o r I n t e g e r2^n1

2PrintQ233,1

3PrintQ377,1

4PrintQ4153,1,5,1

5PrintQ53131,1

6PrintQ6633,2,7,1

7PrintQ7127127,1

8PrintQ82553,1,5,1,17,1

9PrintQ95117,1,73,1

10PrintQ1010233,1,11,1,31,1

11PrintQ11204723,1,89,1

12PrintQ1240953,2,5,1,7,1,13,1

13PrintQ1381918191,1

14PrintQ14163833,1,43,1,127,1

15PrintQ15327677,1,31,1,151,1

16PrintQ16655353,1,5,1,17,1,257,1

17PrintQ17131071131071,1

18PrintQ182621433,3,7,1,19,1,73,1

19PrintQ19524287524287,1

20PrintQ201048575

3,1,5,2,11,1,31,1,41,1

21PrintQ2120971517,2,127,1,337,1

22PrintQ2241943033,1,23,1,89,1,683,1

23PrintQ23838860747,1,178481,1

24PrintQ2416777215

3,2,5,1,7,1,13,1,17,1,241,1

25PrintQ253355443131,1,601,1,1801,1

26PrintQ26671088633,1,2731,1,8191,1

27PrintQ271342177277,1,73,1,262657,1

28PrintQ28268435455

3,1,5,1,29,1,43,1,113,1,127,1

29PrintQ29536870911233,1,1103,1,2089,1

30PrintQ301073741823

3,2,7,1,11,1,31,1,151,1,331,1

31PrintQ3121474836472147483647,1

32PrintQ324294967295

3,1,5,1,17,1,257,1,65537,1

33PrintQ338589934591

7,1,23,1,89,1,599479,1

34PrintQ34171****91833,1,43691,1,131071,1

35PrintQ3534359738367

31,1,71,1,127,1,122921,1

36PrintQ36687194767353,3,5,1,

7,1,13,1,19,1,37,1,73,1,109,1

37PrintQ37137438953471223,1,616318177,1

38PrintQ382748779069433,1,174763,1,524287,1

39PrintQ39549755813887

7,1,79,1,8191,1,121369,1

40PrintQ4010995116277753,1,5,2,

11,1,17,1,31,1,41,1,61681,1

41PrintQ41219902325555113367,1,164511353,1

42PrintQ424398046511103

3,2,7,2,43,1,127,1,337,1,5419,1

43PrintQ438796093022207

431,1,9719,1,2099863,1

44PrintQ44175921860444153,1,5,1,

23,1,89,1,397,1,683,1,2113,1

45PrintQ4535184372088831

7,1,31,1,73,1,151,1,631,1,23311,1

46PrintQ4670368744177663

3,1,47,1,178481,1,2796203,1

47PrintQ47140737488355327

2351,1,4513,1,13264529,1

48PrintQ482814749767106553,2,5,1,7,1, 13,1,17,1,97,1,241,1,257,1,673,1

49PrintQ49562949953421311127,1,4432676798593,1

50PrintQ5011258999068426233,1,11,1, 31,1,251,1,601,1,1801,1,4051,1

51PrintQ512251799813685247

7,1,103,1,2143,1,11119,1,131071,1

52PrintQ5245035996273704953,1,5,1,

53,1,157,1,1613,1,2731,1,8191,1

53PrintQ539007199254740991

6361,1,69431,1,20394401,1

54PrintQ5418014398509481983

3,4,7,1,19,1,73,1,87211,1,262657,1

55PrintQ5536028797018963967

23,1,31,1,89,1,881,1,3191,1,201961,1

56PrintQ56720575940379279353,1,5,1,17,1, 29,1,43,1,113,1,127,1,15790321,1

57PrintQ57144115188075855871

7,1,32377,1,524287,1,1212847,1

58PrintQ582882303761517117433,1,59,1, 233,1,1103,1,2089,1,3033169,1

59PrintQ59576460752303423487

179951,1,3203431780337,1

60PrintQ601152921504606846975

3,2,5,2,7,1,11,1,13,1,31,1,

41,1,61,1,151,1,331,1,1321,1

61PrintQ612305843009213693951

2305843009213693951,1

62PrintQ624611686018427387903

3,1,715827883,1,2147483647,1

63PrintQ6392233720368547758077,2,

73,1,127,1,337,1,92737,1,649657,1

64PrintQ64184467440737095516153,1,5,1, 17,1,257,1,641,1,65537,1,6700417,1

65PrintQ6536893488147419103231

31,1,8191,1,145295143558111,1

66PrintQ66737869762948382064633,2,7,1,23,1, 67,1,89,1,683,1,20857,1,599479,1

67PrintQ67147573952589676412927

193707721,1,761838257287,1

68PrintQ682951479051793528258553,1,5,1, 137,1,953,1,26317,1,43691,1,131071,1

69PrintQ69590295810358705651711

7,1,47,1,178481,1,10052678938039,1

70PrintQ701180591620717411303423

3,1,11,1,31,1,43,1,71,1,

127,1,281,1,86171,1,122921,1

71PrintQ712361183241434822606847

228479,1,48544121,1,212885833,1

72PrintQ724722366482869645213695

3,3,5,1,7,1,13,1,17,1,19,1,37,1, 73,1,109,1,241,1,433,1,38737,1

73PrintQ739444732965739290427391

439,1,2298041,1,9361973132609,1

74PrintQ7418889465931478580854783

3,1,223,1,1777,1,25781083,1,616318177,1

75PrintQ75377789318629571617095677,1,31,1, 151,1,601,1,1801,1,100801,1,10567201,1

76PrintQ76755578637259143234191353,1,5,1, 229,1,457,1,174763,1,524287,1,525313,1

77PrintQ77151115727451828646838271

23,1,89,1,127,1,581283643249112959,1

78PrintQ783022314549036572936765433,2,7,1, 79,1,2731,1,8191,1,121369,1,22366891,1

79PrintQ79604462909807314587353087

2687,1,202029703,1,1113491139767,1

80PrintQ801208925819614629174706175

3,1,5,2,11,1,17,1,31,1,

41,1,257,1,61681,1,4278255361,1

81PrintQ8124178516392292583494123517,1,73,1, 2593,1,71119,1,262657,1,97685839,1

82PrintQ8248357032784585166988247033,1, 83,1,13367,1,164511353,1,8831418697,1

83PrintQ839671406556917033397649407

167,1,57912614113275649087721,1

84PrintQ8419342813113834066795298815

3,2,5,1,7,2,13,1,29,1,43,1,113,1, 127,1,337,1,1429,1,5419,1,14449,1

85PrintQ8538685626227668133590597631

31,1,131071,1,9520972806333758431,1

86PrintQ86773712524553362671811952633,1, 431,1,9719,1,2099863,1,2932031007403,1

87PrintQ871547425049106725343623905277,1,233,1, 1103,1,2089,1,4177,1,9857737155463,1

88PrintQ88309485009821345068724781055

3,1,5,1,17,1,23,1,89,1,353,1,

397,1,683,1,2113,1,2931542417,1

89PrintQ89618970019642690137449562111

618970019642690137449562111,1

90PrintQ901237940039285380274899124223

3,3,7,1,11,1,19,1,31,1,73,1,

151,1,331,1,631,1,23311,1,18837001,1

91PrintQ912475880078570760549798248447127,1, 911,1,8191,1,112901153,1,23140471537,1

92PrintQ924951760157141521099596496895

3,1,5,1,47,1,277,1,1013,1,

1657,1,30269,1,178481,1,2796203,1

93PrintQ939903520314283042199192993791

7,1,2147483647,1,658812288653553079,1

94PrintQ9419807040628566084398385987583

3,1,283,1,2351,1,4513,1,

13264529,1,165768537521,1

95PrintQ953961408125713216879677197516731,1, 191,1,524287,1,420778751,1,30327152671,1

mathematica实验五 素数

数学实验报告 实验五素数 实验目的： 本次实验将探讨素数的规律及其相关有趣的问题，具体，我们研究以下问题：素数的判别、构造生成素数的公式等。 通过本次实验激发对数论的好奇心，使我们对自然数的神奇规律而折服，同时使我们认识到探索自然数规律的艰难性。 实验步骤： 1、利用Eratosthenes筛法，通过计算机编程求1000以内的所有的素数。 2、利用试除方法，通过计算机编程求1000以内的所有的素数。

3、计算所有小于等于n的素数的个数。（n=1000，10000） n=1000时，程序如右：] Pr imePi [ 1000 运行结果：168 n=10000时，程序如右：] [ Pr imePi 10000 运行结果：1229 4、计算b a被n整除所得的余数。（a=2，b=7，n=6）和（a=3，b=5，n=48） n=6时,程序如右：]6,7,2[ PowerMod 运行结果： 2 n=48时,程序如右：]48,5,3[ PowerMod 运行结果： 3 5、判断Mersenne数的素性。

程序如下: False]]] T rue, 0, If[u M]]; 2, - Mod[u^2 u ,i 1,-n i 1, For[i 1; -n 2^ M False, PrimeQ[n], If[! 4}, u i, {M, Module[ : _Integer]Mersenne[n ===++<==== 当n=127时，输出结果: True 当n=48时，输出结果： False 6、 令dx x n Li n ?=2log 1)(，!)(log )1(11)(1k n k k n R k k ∑∞=++=ζ，其中?+++=k k k 31211)(ζ。试对一 系列充分大的n,计算),(n π),log(/n n ),083660.1)/(log(-n n ).()(n R n Li 及其中哪一个公式最接近)(n π？ 程序如下： 100000}] 900000, 100000, {i, [i],Do[Compare ] Print[t] R]; ,AppendT o[t Li]; ,AppendT o[t ; 1.08366)]] - 100000] Log[E,N[100000/( ,AppendT o[t 100000]]]; og[E,N[100000/L ,AppendT o[t 0000]]; PrimePi[10 ,AppendT o[t ; Infinity}] 2, {k, l[k],k/Factoria 100000]^ Log[E,*1] eta[k NSum[1/k/Z 1 R 100000}]; 2, {x, x],[1/Log[E,NIntegrate Li {}}, t k, Module[{x,100000 : Integer]Compare[n_++==== 运行结果：9592, 8685.89, 9588.4, 9628.76, 9580.43 观察得到最接近)(n π的是)083660.1)/(log(-n n 。 实验总结： 通过本次实验，掌握了如何求素数，以及关于素数的一些知识。充分激发了对数论的好奇心，从而也认识到探索自然数规律的艰难性。

关于素数研究的实验报告

1 问题及算法 1.1 问题描述 为了解决普通算法无法正确求出大素数的问题，我们现在用改进后的Miller-Rabin算法来很好的解决了大素数的问题。 1.2 算法思路描述 由费马小定理知：若n是素数，则对所有1≤a≤n-1的整数a，有a^(n-1)mod n=1。该定理的逆否命题也成立，即a^(n-1)mod n!=1，则n为合数。但是费马定律的逆命题就不一定成立了，比如当a=4，n=15时,4^14mod15=1,但是4不是素数而是合数。也就是说直接用费马定理求解素数的话，是有一定的错误率的，现在我们的目标的尽量减少错误率。 从大量数据统计来看，如果满足a^(n-1)mod n=1，则n较大概率为素数.那么，我们把那些使得n原本为合数而被看成素数的a叫做伪证据，称n为伪素数。同样从大量数据看出有些伪素数n有很多伪证据a，比如当n=561，a有318个可使得结果判为素数。所以，我们定义了强伪素数概念： 设n是一个大于4的奇整数，s和t是使得(n-1)=2^s*t的正整数，其中t为奇数，设B(n)是如下定义的整数集合： a属于集合B(n)当且仅当2≤a≤n-2且 1．a^tmodn=1 2．存在整数i，0≤i

当n为合数时，若a属于集合B(n)，则称n为一个以a为底(基)的强伪素数，称a为n素性的强伪证据。 n为素数，说明它对所有底均为强伪素数。 通过这一定义则发现，小于1000的奇合数中，随机选到一个强伪证据的概率小于1%。更重要的是，对任一奇合数，强伪证据比例都很小。所以,我们可以多次运行下面的算法,就可把错误概率降低我们可控制的范围，这样我们就有效的解决了大素数求解的问题。1.3 算法实现的关键技巧 此算法实现的关键技巧在于强伪素数的定义以及巧妙的应用。 Btest(a，n){ //n为奇数，返回true。即返回真说明n是强伪素数 s←0；t ←n-1；//t开始为偶数 repeat s++；t ←t÷2； until t mod 2 = 1；//n-1=2st t为奇数x ←at mod n； if x=1 or x=n-1 then return true;//满足强伪素数定义1或者2. for i ←1 to s-1 do{ x ←x2 mod n； if x=n-1 then return true；//满足强伪素数定义2 } return false；}

实验三实验报告

素性检验、素数生成与RSA 算法的实现 学号：023421031 姓名：陈建湘 班级：科计A 班 2005-6-5 摘要：非对称密码体制RSA 在数字签名和认证中得到了普遍的应用，但是其体 制本身与大素数的生成有着紧密的联系，由此而产生的素性检验，大素数生成算法等的研究与探讨受到了密码学界的广泛重视。本文介绍了一种Solovay Strassen 算法来检验奇整数的素性，它回答错误的概率与询问的次数有关，可以通过实际测试数据对理论上的估计进行验证。基于此种算法可以定义C ＋＋的超长整数Long 类，并构造大素数发生器来实现RSA 算法，同时通过中国剩余定理可以提高解密的效率。 关键字：欧拉伪素数、Solovay Strassen 算法、Long 类③、素数发生器、RSA 、 中国剩余定理 1. 检验以下陈述：若n 是任意的奇合数，则“n 是对于基底a 的欧拉伪素数” 至多对于一半的整数a ∈Zn*成立。 基本假设：问题1，2所进行的检验都在n ≤40000的范围内进行，因为C ＋＋里面最长的十进制正整数（long 型）为2147483647，验证中有一个反复平方乘算 46340≈，所以取40000范围内的整数C ＋＋编译系统能够识别，不会超界。 从后面的3，4问题中可以看到，其实这个假设并不是重要的，因为可以通过自己定义一个超长十进制整数类（class Long ）来验证超过46340的整数。 对于一个奇合数我们可以通过两个奇数相乘得到，所以我在算法中给了两个参数b ，c 来定奇合数n 的界，n 的最大值max （n ）<=b*c ，而a ∈Zn*的求得可以通过调用Inverse （a ，n ）算法求a 模n 逆是否存在来判断，当然Inverse 算法需要调用扩展的Euclidean 算法，以下是检验的结果 当b=10，c=10时，n ∈ [3,100]，max(|Bogusprime|/|Zn*|)=0.25 当 n=15； 当b=100，c=100时，n ∈ [3,10000]，max(|Bogusprime|/|Zn*|)=0.5 当 n=1729； 这里|Bogusprime|代表欧拉伪素数的个数，|Zn*|代表n 中存在模n 逆的元素个数，从结果可见最大值确实没有超过一半即0.5。 2. 记事件a ： “一个特定长度的随机奇数n 是合数。” 记事件b ： “算法连续m 次均判别n 是素数。” 检验：条件概率P[b|a]≤2m -； 条件概率P[a|b] ≤ 1 ln 2 ln 22m n n +--+ 这里可以调用Solovay Strassen 算法来检验，它本身是一个偏是的Monte Carlo 算法，是基于判断奇整数的Jacobi 符号的算法。即如果回答是合数则原奇

素数环问题实验报告

素数环问题实验报告 一、问题分析及算法思路 该题的目的是让我们设计算法实现重新排列从1到20这20个数,使这20个 数排列成一个圆并且相邻两位的和是素数。 这是一个组合问题,利用回溯法可以很好地解决问题。我们可以用一长度为 20的一位数组A[20]来存储这个圈,再用一长度为20的一位数组B[20]来标记一个数是否已经在素数环内了,然后逐渐确定对应每一个位置的数。因为这是一个圈,没有次序问题(指从哪里先开始),我们可以始终使A[0]=1,逐渐确定A[1],A[2]……便可以最终确定出这个素数圈。 在设计算法时,我们可以选用递归回溯,回溯的剪枝函数是判断后面的数与前 一个数之和是否为素数。具体实施情况为:首先A[0]已经确定了,然后确定A[1],要求是A[0]+A{1]是素数且当前A[1]没有在素数环里出现,如果当前A[1]不满足条件,就继续寻找下一个A[1];如果确定了A[i],就继续寻找A[i+1];重复此操作直到确 定A[19],此时检查A[0]+A[19]是否为素数,若是就输出A数组,否则不执行任何操作。 二、算法的程序实现 该算法的程序实现: #include #include using namespace std; ofstream output("OUTOUT.txt");

int A[20]={0};//存储排好序后的数列 int B[20]={0};//标记对应的数是否已经在序列int SU(int n) { int i=2,flag=0; for(i=2;i<=n/2;i++) if(n%i==0) { flag=1; break; } if(flag) return 0; else return 1; }//判断一个数是否为素数,是素数返回1 void Handle(int k)//k表示正在寻找第k+1个数

数字序列实验报告

数字序列实验报告 数字序列实验报告 引言 数字序列是数学中一种重要的研究对象，它们在各个领域都有广泛的应用。本实验旨在通过对数字序列的实验研究，探索其中的规律和特点，并对其应用进行探讨。 实验一：斐波那契数列 斐波那契数列是一种经典的数字序列，它的定义方式是：第一个数是0，第二个数是1，从第三个数开始，每个数都是前两个数之和。通过编写程序，我们生成了斐波那契数列的前100个数。 实验结果显示，斐波那契数列呈现出一些有趣的特性。首先，数列中的每个数都是前两个数的和，这种递推关系使得数列中的每个数字都与前面的数字有着密切的联系。其次，斐波那契数列的增长速度逐渐加快，数列中的数字呈现出明显的指数增长趋势。这种特点在生物学、金融学等领域中都有重要的应用。实验二：等差数列 等差数列是指数列中的每个数与前一个数的差值都相等的数列。我们选择了一个等差数列进行实验研究，通过观察数列的规律和特点，我们可以更好地理解等差数列的性质。 实验结果表明，等差数列具有明显的规律性。首先，数列中的每个数与前一个数的差值都相等，这种规律使得数列中的数字之间有着稳定的关系。其次，等差数列的增长速度是恒定的，数列中的数字呈现出线性增长的趋势。这种特点在物理学、经济学等领域中有着重要的应用。

实验三：等比数列 等比数列是指数列中的每个数与前一个数的比值都相等的数列。我们选择了一 个等比数列进行实验研究，通过观察数列的规律和特点，我们可以更好地理解 等比数列的性质。 实验结果显示，等比数列也具有明显的规律性。首先，数列中的每个数与前一 个数的比值都相等，这种规律使得数列中的数字之间有着稳定的关系。其次， 等比数列的增长速度是不断加快或减慢的，数列中的数字呈现出指数增长或衰 减的趋势。这种特点在物理学、生物学等领域中有着广泛的应用。 实验四：素数序列 素数序列是指仅能被1和自身整除的正整数序列。我们选择了一个素数序列进 行实验研究，通过观察数列的规律和特点，我们可以更好地理解素数的分布规律。 实验结果表明，素数序列呈现出一些有趣的特性。首先，素数序列中的数字之 间并没有明显的规律，它们的分布是随机的。其次，素数序列中的数字在数值 上逐渐增大，但增长速度相对较慢。这种特点在密码学、计算机科学等领域中 有着重要的应用。 结论 通过对不同类型的数字序列进行实验研究，我们发现了它们各自的规律和特点。斐波那契数列呈现出指数增长的趋势，等差数列呈现出线性增长的趋势，等比 数列呈现出指数增长或衰减的趋势，素数序列的分布是随机的。这些规律和特 点在不同领域中都有着广泛的应用，对于我们深入理解数学和应用数学具有重 要意义。

质数白盒测试实验报告

苏州科技学院天平学院 软件测试报告 题目 质数白盒测试 专业年级计算机工程 班级 学号 姓名 成绩 指导教师 2015年3月30 日

质数白盒测试实验报告 1.实验目的 a)能熟练应用功能性测试技术进行测试用例设计； b)对测试用例进行优化设计。 2.实验内容 a)针对实验题目编写的源代码进行白盒测试。要求绘制出程序的 控制流图，采用基路径测试方法和覆盖测试方法设计测试用 例。执行测试用例，并分析测试结果。 3.实验题目 a)输入一个1-100之间的数字，判断该数字是否为质数。 4.实验过程 1.代码和控制流图 1.import java.util.Scanner; 2.public class One_thr { 3.public static void main(String[] args) { 4.System.out.println("输入1--100之间的一个数\n"); 5.Scanner nu =new Scanner(System.in); 6.int i; 7.int a=nu.nextInt(); 8. if(a!=1) 9. { 10.for(i=2;i

15. System.out .printf("%d 不是质数\n",a); 16. else 17. System.out .printf("%d 是质数\n",a); 18. } 19. else 20. System.out .printf("%d 是质数\n",a); 21. } 22. } 2.基本路径测试和覆盖测试 环形复杂度：4+1=5； 路径1:7-8-19-21 路径2:7-8-10-13-14-16-18-21 路径3:7-8-10-11-13-14-15-18-21 路径4:7-8-10-11-10-13-14-16-18-21 路径5:7-8-10-11-10-11-13-14-15-18-21 7 8 10 19 11 13 14 15 16 18 21

数学实验实验报告-素数的分布

素数的分布 一、 实验目的 只有1和它本身两个自然数作为因数的大于1的整数称为素数。本实验将通过计算机发现素数的规律及素数的一些有趣现象和性质，具体地我将研究有关素数的下列问题： ◆ 素数分布的几何与数值观察 ◆ 利用数学软件求素数 ◆ 素数分布的规律性 通过此次试验对素数的分布进行深入研究，窥探数学的奥秘。 二、 实验环境：Mathematica8.0 三、 实验内容和步骤及其对得到结果的分析 实验1：素数分布的几何与数值观察 如果一个大于1的自然数只能被1及它本身整除，则该数称为素数。否则被称为合数。从数学史的黎明时期开始，数学家一直在探索自然数的奥秘，远在古希腊时代，欧几里德就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分解时唯一的，这就是算术基本定理。算术基本定理表明，素数是构造自然数的基石，正如物质的基本粒子一样。 首先，我们不禁要问：素数到底有多少个？会不会在某一充分大的自然数以后就没有素数了呢？答案是否定的，欧几里德时代已经证明了这一结论。他使用的简洁而优美的论证方法至今仍不失为数学推理的光辉典范。假设素数只有有限个，按从小到到达的顺序排列为12,,n p p p 。令121n N p p p =+ ，则N 不被 ,1,2,,i p i n = 中任何一个整除。因而，N 要么是素数，要么有比n p 大的素因子，这与n p 为最大素数相矛盾。 程序1：素数分布的几何 用()x π表示不超过x 的素数，画出（n ，π（x ）），n=1，2，…，m 的点阵图，观察素数的分布。 程序代码如下：

运行程序1，得到下图 从图可以看到，素数应该有无穷多个，且随着n的增大，π（n）是增大的。 实验2：利用数学软件求素数 程序2：直接利用Mathematica8.0求出素数 程序代码如下： 得到如下结果： …程序3：利用Eratosthenes筛法，求10000以内的所有素数： 古希腊有一位学者Eratosthenes给出了解决这一问题的方法，这一方法被后人称为Eratosthenes筛法。 Eratosthenes筛法的基本思想是，将自然数从2开始按顺序排列至某一整数N。首先，从上述数列中划去所有2的倍数（不包含2）。在剩下的数中，除2

实验报告

实验报告 实验六 6.1范例：修改实验五中的第二题，求出水仙花数后不是在屏幕上显示而是存入文本文件。请在退出程序后，用记事本打开该文本文件，查看结果 程序： #include using namespace std; int main(){ int k=100,l,m,n,count=0; ofstream ofile; ofile.open("myfile.txt"); ofile<<"水仙花数有："< using namespace std; void main(){ int i,j,m,p,k; for(i=100;i<1000;i++){ m=i%10; p=i/10-10*(i/100); k=i/100; j=m*m*m+p*p*p+k*k*k; if(i!=j) continue; else cout<

6.2．范例：编程从上题生成的文本文件读取水仙花数，并显示在屏幕上。 程序： #include #include using namespace std; int main(){ char ch[256]; fstream ifile; ifile,open(",,\\Exp6_1\\myfile.txt"); cout<<"文件内容:"<a。将所有符合要求的组合存入文本文件中。 4.编写程序从上题建立的文本文件中读取500以内的勾股弦数并显示在屏幕上。

素数检测算法报告

素数检测算法的学习报告 素数是指在自然数中,除了1和它自身外,没法被其他自然数整除的数。在这几天查阅书籍和一些相关的网络资源中,对素数的检测算法有了很深入的了解,因为大部分资料是在网上找到的,所以将“读书报告”改为“学习报告”,望老师谅解。 对于素数的检测算法有很多,先前有很多人研究过这些,我相信以后还会有很多人来研究,以下内容是我国庆这几天,在空闲时读到的算法的一个总结。 1.试除法来判定素数。 这种方法是我们常用的方法,思路是用循环将已知数与比其小的数相除,判断余数是否为零,为零则不是素数,不为零则为素数。相关代码如下: #include #include "math.h" void main() { int i,k,n; int flag=1; cout<<"输入一整数:"<>n; k=sqrt(n); //用n除以比他小的每一个也可以,实际除以n的开方就可以 for(i=2;i<=k;i++)

if(n%i==0) { flag=0; cout<<"此数不是素数!"< #include "math.h" void prime(int n); void main()

数学实验报告5

实验报告5 实验名称 素数 实验目的 探讨素数的规律及其相关的某些有趣问题，激发人们对数论的好奇心，使人们认识到自然数的神奇规律与探索自然数规律的艰难性。 实验环境 Mathematica 4 实验内容 1. 利用Eratosthenes 筛法，通过计算机编程求10000以内的所有素数。 2. 利用试除方法，通过计算机编程求10000以内的所有素数，试将试除法与筛法进行比较，哪一个更有效？ 3. 给出小于等于n 的素数的个数。 4.令 dx x n Li n ⎰ =2 log 1 )(， !)(log )1(11)(1 k n k k n R k k ∑ ∞ =++=ξ， 其中 +++ =k k k 3 1 211)(ξ. 试对一系列充分大的n ，计算R(n),)(),08366 .1)/(log(),log(/(n),n Li n n n n -π.其中哪一个公式更接近(n)π? 实验的基本理论和方法

1. Eratosthenes 筛法的基本思想:将自然数列从2开始按顺序排列至某一整数N 。首先，从上述数列中划去所有2的倍数（不包括2）。在剩下的数中，除2外最小的是3.接着，从数列中划掉所有3的倍数（不包括3）。然后，在剩下的数中再划掉5的倍数……。这一过程一直进行下去。则最后剩下的数就是不超过N 的所有素数。 2. 试除方法的基本思想:假设我们已经找到了前n 个素数 ,,,3,221n p p p ==为了寻找下一个素数我们从2+n p 开始依次检验 每一个整数N ，看N 是否被某个n i p i ,,2,1, =整除。如果N 能被前面的某个素数整除，则N 为合数。否则N 即为下一个素数1+n p 。实际上，为了提高算法的效率，我们不需要用前面的每一个素数去试除N ，而只需要用不超过N 的素数去除就可以了。 实验步骤 1. 在Mathematica 4软件中输入以下程序： Sieve[n_Integer]:= Module[ {t={},i,temp}, For[i=2,i<=n,i++,AppendTo[t,i]]; For[i=1,Prime[i]<=Sqrt[n],i++,temp=Prime[i];t=Select[t,(#1==temp||Mod[#1,temp]!=0)&]];t]; Sieve[10000] 2. 在Mathematica 4软件中输入以下程序： DivPrime[n_Integer]:=

实验名称 计算出1000以内10个最大素数之和

实验名称计算出1000以内10个最大素数之和 实验目的 1、熟练掌握if、if…else、if…else if语句和witch语句格式及使用方法，掌握if语句中的嵌套关系和匹配原则，利用if语句和switch语句实现分支选择结构。 2、熟练掌握while语句、do…while语句和for语句格式及使用方法，掌握三种循环控制语句的循环过程以及循环结构的嵌套，利用循环语句实现循环结构。 3、掌握简单、常用的算法，并在编程过程中体验各种算法的编程技巧。进一步学习调试程序，掌握语法错误和逻辑错误的检查方法。 实验内容 计算并输出1000以内最大的10个素数以及它们的和。 要求： 在程序内部加必要的注释。 由于偶数不是素数，可以不考虑对偶数的处理。 虽然在1000以内的素数超过10个，但是要对1000以内不够10个素数的情况进行处理。输出形式为：素数1＋素数2＋素数3＋…＋素数10＝总和值。 算法描述流程图 Main函数： 判断素数： 源程序 #include #include int sushu(int n)/* 判断素数的函数*/ { int t,i; t=sqrt(n); for(i=2;i<=t;i++) if(n%i==0)/* 如果不是素数，返回0 */ return 0;

return n;/* 如果是素数，返回该数*/ } void main() { int i,j=0,n,m=0,a[1000],x; /*clrscr();*/ printf("Please input a number form 1 to 1000:"); scanf("%d",&x); if(x==2)/* x=2时的处理*/ printf("%d\n",x); else if(x<=1) /* x在1～1000范围外时的处理*/ printf("Error!\n"); else { if(x%2==0)/* x为偶数时，把x变为奇数*/ x--; for(i=x;i>1;i-=2)/* x为奇数时，做函数计算*/ { n=sushu(i); /* 做判断素数的函数调用*/ if(n!=0)/* 对素数的处理*/ {

数学实验报告 素数

数学实验报告 关于素数的探讨 一、实验目的 如果一个大于1的自然数只能被1及它本身整除，则该数称为素数。我们可以很快判断一个很小的自然数是否为素数，但如果判断一个大的自然数就有些困难，本实验就是通过数学工具及数学方法来解决一些有关素数的问题，让我们更加了解素数及其分布规律。需要解决的实验如下： 1，如何判断1234567是否为素数 2，生成素数表（500以内） 3，探讨素数的分布规律 二、问题求解方法 由素数的定义可知如果一个数不能被大于1小于它本身的所有数整除，则可判断该数为素数，根据这种思想可以用C语言编程来判断1234567是否为素数；每一个合数都可以分解为若干个素数的乘积，如果想生成500以内的素数表，可以将2到500的数列中依次划去所有2的倍数，接着划去3的倍数，再划去5的倍数······这样一直进行下去就可以得到500以内的素数。也可以用不超过√N考虑

到500不是很大，可以先手工编写500以内的素数表，然后分别用c 语言和Mathematic程序生成素数表，并总结素数的分布规律。 三、程序设计流程 1，判断1234567是否为素数的c语言程序： #include void main() {int a=1234567,b=2; while(a%b!=0) b++; if(b void main() {int a=3,b=2,c; for(a=3;a<500;a++) {for(b=2;b<=a;b++) if(a%b==0) break; if(b==a) printf("%d\n",a);} }

数学实验报告 实验五

数学实验报告 实 验 五 学院：数学与统计学院 班级：信息与计算科学(1)班 姓名：郝玉霞 学号：201171020107

实验五 一．实验名称: 素数。 二．实验目的: 理解素数的含义及其性质,并能熟练的运用素数的判别与求解、生成素数的公式、素数的分布；掌握素数的规律及相关的某些有趣问题；通过本实验，我们将掌握素数的判别方法，并会求解某些范围内的素数，通过编程演示某些范围内的素数，深刻了解其求解过程，还可以通过上机来增强自己的动手能力及实践创新能力。 三．实验环境: 学校机房，Mathematica 软件。 四．实验的基本理论和方法： 1. Eratosthenes 筛选法：此方法的基本思想是，将自然数列从2开始按顺序排列至某一整数N 。首先，从上述数列中划去所有2 的倍数（不包括2）。在剩下的数中，除2外最小的是3.接着，从数列中划去所有3的倍数（不包括3）。然后在剩下的数中，再划去5的倍数…….这个过程一直进行下去，则最后剩下的数就是不超过N 的所有素数。 2.试除法：假设已经找到了前n 个素数21=p ，32=p ，…，n p ，为了寻找下一个素数我们从2+n p 开始依次检验每一个整数N ，看N 是否能被某个 n i p i ,,2,1, =整除。如果N 能被前面提到的某个素数整除，则N 为合数。否则N 即为下一个素数1+n p 。 3.n-1检验法：假设n-1=FR ，其中F>R 且gcd(FR)=1.如果对F 的每一个素因子q 都存在一个整数a>1满足()n a n mod 11 ≡-且()1,1gcd 1=⎪⎭ ⎫ ⎝⎛--n a q n ， 则n 是素数。 五．实验内容和步骤及结果和结果分析 实验1：分别用筛选法和试除法求所有小于等于n 的素数 实验内容： ㈠利用Eratosthenes 筛法，通过计算机编程求出1000以内的所有素数。 语句：

数学实验素数

素数 姓名： 学号： 班级：数学与应用数学4班

实验报告 实验目的：素数(Prime)是构造所有数的“基本材料”，犹如化学上的化学元素和物理学中的基本粒子，有关素数的许多看似简单却极富刺激性的奇妙问题，向一代代数学家提出了挑战，始终吸引着他们的目光。本实验将探讨素数的规律及其相关的某些有趣问题，如素数的判别，求素数的个数等。 实验环境：Mathematica软件 实验基本理论和方法： 素数：如果一个大于1的自然数只能被1及它本身整除，则该数称为素数，否则被称为合数。 算数基本定理：从数学史的黎明时期开始，数学家就一直在探索自然数的奥秘，远在古希腊时代，欧几里得就证明了每一个合数都可以分解为若干个素数的乘积，并且在不计较素数排列顺序时这种分解是唯一的，这就是所谓的算数基本定理。算数基本定理表明素数是构造自然数的基石，正如物质的基本粒子一样。 Mathematica的素数函数：Mathematica系统提供了两个常用的与素数有关的函数：（1）[n]，就是返回从第一个素数2数起的第n个素数；（2）PrimeQ[n]，就是判断自然数n是否为素数，是则返回True，否则返回False。 使用系统函数输出某个指定范围内的所有素数，只要定义如下的函数即可：

筛法求素数：2000多年前，希腊学者埃拉托色尼(Eratosthenes 公元前约284-192年)给出了一个寻找素数的简便方法—筛法：写下从2、3、…、N，注意到2是一个素数，划去后面所有2的倍数，越过2，第一个没有被划去的数是3，它是第二个素数，接下来再划掉所有3的倍数，3之后没有被划去的数是5，然后再划掉除5外所有5的倍数，以此类推。显然，划掉的都是较小整数的倍数，它们都不是素数，都被筛掉了，而素数永远不会被筛掉，它们就是要寻找的不超过N的所有素数。 试除法求素数：假设我们已经找到了前n个素数，为了下一个素数我们从开始一次检验每一个整数N，看N是否能被某个整除。如果N能被前面的某个素数整除， 则N为合数，否则N即为下一个素数。实际上，为了提高算法的效率，我们不需用前面的每一个素数去试除N，而只需用的素数去除 就可以了。 素数的判断方法：判断一个正整数n是否是素数，只要将n分别除以2到n之间的各个整数，如果n都不能被整除，则n为素数。程序为： （当n是素数，返回“True”；若不是素数，返回“False”。） 费尔马小定理：当n为素数且m不被n整除时，被n整除的余数都是1，我们用同余记号记之为（意即a与b 被n整除的余数相同）。但费尔马小定理的逆定理不成立，即由

2021年素数实验报告

素数 一．试验解读 假如一个大于1 自然数只能被1及它本身整除, 则称该数为素数, 不然称为合数。每一个合数都能够分解为若干个素数乘积, 而且在不计较素数排列次序时这种分解是唯一, 这就是所谓算术基础定理。 Mersenne数与Fermat数是两种含有特殊结构数。Mn=2^n-1, Fn=2^(2^n)+1。 假如将素数在数轴上标出来, 会发觉素数分布很不规则。我们需做试验深入观察伴随整数范围扩大, 素数是越来越稀还是越来越密？ 相关素数还存在许很多多富于挑战性问题, 如Goldbach猜想; 大整数素因子分解; 完全数; 孪生素数ertrand B猜想; 青一色数素数 二．试验思绪 1.素数判别与个数 在大于1自然数中, 只能被1和它本身整除数称为素数。 要求Nn=p1p2......pn+1, 当n=1,...,20时判定Nn是否是素数, 假如不是, 那么Nn能不能表示成多个素因子相乘形式。改变n取值范围, 观察得出结论。 依据以上结果, 猜测素数是否有没有穷多个, 并给出相关证实。 2素数表结构 用Eratosthenes筛法和试除法列出1000内全部素数, 比较哪种方法所用时间比较少。它们原理为: Eratosthenes筛法基础原理, 将自然数列从2开始按次序排列至某一整数N, 首先, 从上述数列中划除全部2倍数（不包含2）, 在剩下数中, 除2外最小是3.接着, 从数列中划除全部3倍数（不包含3）, 然后在剩下数中, 再划去5倍数······ 这个过程一直进行下去, 则最终剩下数就是不超出N全部素数。 试除法基础原理: 假设我们已经知道前n个素数p1=2,p2=3,...,pn, 为找下个素数, 我们从pn+2开始依次检验每一个整数N, 看是否能被某一个pi(i=1,2,...,n)整除, 若N能被前面某个素数整除, 则N为合数, 不然N即为下一个素数pn+1。为了提升效率我们只需要用不超出N^(1/2)素数去除就能够了. 3素数判别公式 对n=2 ,3 ,…, 100中不一样数,观察m ^( n - 1)被n整除所得余数。 将m值固定, 改变n值为2, 3, (100) 取m=2, 观察2 ^( n - 1)被n整除所得余数 取m=3, 观察3 ^( n - 1)被n整除所得余数