素数计算
计算素数
☆题目30
请编写一个函数jsV alue(int m,int k,int xx[])，该函数的功能是：将大于整数m且紧靠m的k 个素数存入数组xx传回。
最后调用函数writeDat()读取10组数据，分别得出结果且把结果输出到文件out.dat中。
部分源程序存在文件prog1.c中。
例如：若输入17 5 则应输出：19，23，29，31，37。
请勿改动主函数main()和写函数writeDat()的内容。
int isP(int m)
{
int i;
for(i=2;i if(m % i==0)return 0; return 1; } void num(int m,int k,int xx[]) { int s=0; for(m=m+1;k>0;m++) if(isP(m)) { xx[s++]=m; k--;} ★题目44（素数题） 已知数据文件in.dat中存有300个四位数，并已调用读函数ReadDat()把这些数存入数组a 中，请编制一函数jsV alue()，其功能是：求出所有这些四位数是素数的个数cnt，再求出所有满足此条件的四位数平均值pjz1，以及不满足此条件的四位数平均值pjz2，最后调用写函数writeDat()把结果cnt,pjz1,pjz2输 出到out.dat文件。 例如：5591是素数，则该数满足条件计算平均值pjz1，且个数cnt=cnt+1。 9812是非素数，则该数不满足条件计算平均值pjz2。 int isP(int m) {int i; for(i=2;i if(m%i==0)return 0; return 1; } jsV alue() {int i; for(i=0;i<300;i++) if(isP(a[i])) {pjz1+=a[i];cnt++;} else pjz2+=a[i]; if(cnt==0) pjz1=0; else pjz1/=cnt; if(300-cnt==0) pjz2=0; else pjz2/=(300-cnt); } ★☆题目42（素数题） 下列程序的功能是：找出所有100以内（含100）满足I，I+4，I+10都是素数的整数I（I+10也在100以内）的个数cnt以及这些I之和sum。请编写函数countV alue()实现程序要求的功能，最后调用函数writeDat()把结果cnt和sum输出到文件out.dat中。 int isPrime(int m) { int i; for(i=2; i if(m % i ==0) return 0 ; return 1; } void countV alue() {int i; for(i=2;i<=90;i++) if(isPrime(i)&&isPrime(i+4)&&isPrime(i+10)) {cnt++;sum+=i;} } 运行结果为： 满足条件的整数的个数＝7 满足条件的整数的和值＝201 题目41（素数统计排序题） 已知数据文件in.dat中存有300个四位数，并已调用读函数ReadDat()把这些数存入数组a 中，请编制一函数jsV alue()，其功能是：求出所有这些四位数是素数的个数cnt，再把所有满足此条件的四位数依次存入数组b中，然后对数组b的四位数按从小到大的顺序进行排序，最后调用写函数writeDat()把结果输出到out.dat文件。 例如：5591是素数，则该数满足条件存入数组b中，且个数cnt=cnt+1。9812是非素数，则该数不满足条件忽略。 int isP(int m){ int i; for(i=2;i if(m%i==0)return 0; return 1; } jsV alue() {int i,j,value; for(i=0;i<300;i++) if(isP(a[i])) b[cnt++]=a[i]; for(i=0;i for(j=i+1;j if(b[i]>b[j]) {value=b[i]; b[i]=b[j]; b[j]=value;} } 40 素数题 题目40（素数题) 无忧id 102 题提供了求素数isPrime()函数 程序prog1.c的功能是：选出100以上1000之内所有个位数字与十位数字之和被10除所得余数恰是百位数字的素数（如293）。计算并输出上述这些素数的个数cnt以及这些素数值的和sum。请考生编写函数countV alue( )实现程序要求，最后调用函数writeDA T()把结果cnt 和sum输出到文件bc10.out中。 int isPrime(int m) { int i; for(i=2;i if(m % i==0)return 0; return 1; } void countV alue() { int i,j,bw,sw,gw; for(i=100;i<1000;i++) { bw=i/100; sw=i%100/10; gw=i%10; if(isPrime(i)&&(gw+sw)%10==bw) { cnt++; sum+=i;} } } ★题目43（素数题） 下列程序prog1.c的功能是：计算500-800区间内素数的个数cnt，并按所求素数的值从大到小的顺序，再计算其间隔加、减之和，即第1个素数-第2个素数+第3个素数-第4个素数+第5个素数...的值sum。请编写函数countV alue()实现程序的要求，最后调用函数writeDat()把结果cnt和sum，输出到文件OUT11.DA T中。 int isP(int m) { int i; ? for(i=2;i if(m % i==0)return 0; return 1; } void countV alue() {int i,j,k=1; for(i=800;i>500;i--) if(isP(i)) { cnt++; sum=sum+k*i; k=k*(-1); } } } 由于大于2的质数一定是奇数（奇数又不一定都是质数），所以，在判断一个自然数 是不是质数时，首先要看它是奇数还是偶数。如果是大于2的偶数，这个数肯定不是 质数，而是合数；如果是奇数，那就有可能是质数,可以用试除法来判断一个自然数是不是质数。例如判断143、179是不是质数，就可以按从小到大的顺序用2、3、5、7、11……等质数去试除。一般情况下用20以内的2、3、5、7、11、13、17、19这8个质数去除就可以了。如143，这个数的个位是3，排除了被2、5整除的可能性，它各位数字的和是1+4+3=8，也不可能被3整除，通过口算也证明不能被7整除，当试除到11时，商正好是13，到此就可以断定143不是质数。 对179试除过程如下： 179÷2=59 (2) 179÷3=66 (1) 179÷5=35 (4) 179÷7=25 (4) 179÷11=16 (3) 179÷13=13 (10) 179÷17=10 (9) 当179÷17所得到的不完全商10比除数17小时，就不需要继续再试除，而断定179是质数。这是因为2、3、5、7、11、13、17都不是179的质因数，因此，179不会 再有比17大的质因数，或者说179不可能被小于10的数整除，所以，179必是质数 无疑。 综上所述，用试除法判断一个自然数a是不是质数时，只要用各个质数从小到大依次去除a，如果到某一个质数正好整除，这个a就可以断定不是质数；如果不能整除， 当不完全商又小于这个质数时，就不必再继续试除，可以断定a必然是质数。 100以内的质数共有25个，这些质数我们经常用到，可以用下面的两种办法记住它们。 一、规律记忆法 首先记住2和3，而2和3两个质数的乘积为6。100以内的质数，一般都在6 的倍数前、后的位置上。如5、7、11、13、19、23、29、31、37、41、43……只有25、35、49、55、65、77、85、91、95这几个6的倍数前后位置上的数不是质数， //////////////////不同算法的100到999之間的素數代碼！///////////////////////////////////////// #include 孪生素数猜想初等证明详解 齐宸 孪生素数是指相差2的素数对，例如3和5，5和7，11和13…。孪生素数猜想正式由希尔伯特在1900年国际数学家大会的报告上第8个问题中提出，可以这样描述：存在无穷多个素数p，使得p + 2是素数。 素数对（p, p + 2）称为孪生素数。 孪生素数由两个素数组成，相差为2。为了证明孪生素数猜想，无数的数学家曾为之奋斗，但美丽的公主仍然犹抱琵琶半遮面。 1．孪生素数分类及无个位表示方法 孪生素数按两个素数个位不同划分3类（不包括10以下的3-5、5-7），分别是： 1、孪生素数中两个素数个位为1和3，如11-13，41-43等； 2、孪生素数中两个素数个位为7和9，如17-19，107-109等； 3、孪生素数中两个素数个位为9和1，如29-31，59-61等。 三类孪生素数中个位为1和3的第一类是我们需要重点研究的，其他两类可以忽略不计。因为只要第一类孪生素数无限，也就等价于证明了孪生素数猜想。 自有孪生素数概念以来它们就是由两个素数表示的。若是能简化成一个数字那孪生素数猜想这一世界数学难题也许就向前迈进了一步。无论这一步是一小步，还是一大步。但毕竟能将两个素数组成的孪生素数降格成了像素数那样的单个数字。 分析一下个位为1和3的这一类孪生素数，如41-43这对孪生素数。首先，分别去掉个位1和3后，可以看到剩下了两个数字4和4。用这两个数字完全可以表示一对孪生素数，当然我们心里要想着在这两个数字后面是有个位1和3的。其次，这两个去掉个位的数字又是完全相同的，都是一个数字“4”。这样也就完全可以用一个数字“4”来表示一对孪生素数，也可以说4是一个单数字无个位孪生素数。当然表面上看只有第一类、第二类孪生素数可以用一个数字表示（实际上第三类也可以）。 为什么一定要去掉个位呢？ 可将自然数变成互为补集的两类：孪生素数和非孪生素数。并利用一种简单的筛法，将自然数中的非孪生素数及其补集孪生素数分开。而且这个筛法所要得到的是非孪生素数。并用非孪生素数证明孪生素数猜想。 自然数分成互补的孪生素数与非孪生素数，这是一种新的观点。恐怕没有人相信这种新奇的想法，但这是可以实现的。而且还可以将自然数分成互补的四胞胎素数与非四胞胎素数等。 求素数列表和判断素数的算法 有兴趣阅读本文的读者，应该对素数概念是十分熟悉的了。用计算机程序实现素数计算，集中在2个主要问题上： ?判断一个正整数是否是素数-（算法A） ?求一定范围内的素数列表- （算法B） 关于素数的算法，根据素数的数学性质，大家都会想到如下几个方面： ?用遍历求模的方式判断素数 ?素数都是奇数，可以在奇数数列中寻找素数 ?利用开方来缩小搜索的范围 然后，求素数的计算是复杂的，如果算法写得不好，则耗时较高。在百度百科“素数”条目中的算法程序，是值得商榷的。很多方法是O(N2)的算法。 为此，在本文中探讨了求素数列表和判断素数这两个算法，力图使算法可以达到O （N Log(N)）优化级别。在本文中，算法语言选用C#。 1,判断素数的简单实现（算法A-1） /// 1001 害死人不偿命的(3n+1) 猜想（15 分 对任何一个正整数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在1950年的世界数学家大会 上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 (3 n+1) ，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展?? 我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？ 分析：输入一个正整数 n 进行循环， n=1 循环截止 , 判断 n, 如果它是偶数，那么把它砍掉一半； 如果它是奇数，那么把 (3 n+1) 砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1， 并计算经过的次数m。 #include"stdlib.h" #include"stdio.h" int main() { int n,m; m=0; scanf_s("%d",&n); while(n!=1) { if(n%2==0) { n=n/2; } else { n=(3*n+1)/2; } m++; } printf_s("%d\n",m); system("pause"); } 1002 写出这个数（20分） 读入一个正整数n，计算其各位数字之和，用汉语拼音写出和的每一位数字。 分析：输入一个正整数n， while循环求出n的各位数字之和sum；如果 sum 等于 0，那么就输出它的拼音”ling ”；如果不等于0，输入数组 b 存放各位数字之和，在switch对这个数组进行判断数组 b 各个数的数值为多少，0 对应 "ling"; 1 对应 "yi";2:对应<"er";3对应"san";4对应"si";5对应"wu";6对应"liu";7对应"qi";8对应 "ba";9对应"jiu"; #include int m; for(m=1;m<=10;m++) { if(p(m)) printf("%d ",m); } printf("\n"); }*/ //3-100间所素数。 /*main() { int i,n; for(n=3;n<=100;n++) { for(i=2;i<=n-1;i=i+1) if(n%i==0) break; if(i>=n) printf("%d\t",n); } }*/ /*main() { int i,m,j; for(i=2;i<=10;i++) { m=sqrt(i); for(j=2;j<=m;j++) { if(j%m==0) break; if (j>m) //加上这句，如果检查所有的j全部不能整除m，循环结束后，j一定大于m,这时的i才是素数 printf("%d",i); } } } /* void main() { int i,j,n=0,xx[10]; for(i=1;i<10;i++) VB常考算法（三）素数： 1、算法说明 所谓素数是指只能被1和它本身整除的数。 1）判断某数是否为素数。根据循环控制变量来判断。 算法说明：根据素数只能被1和它本身整除的性质，我们可以使用循环依次判断2到n-1（或者Sqr(n)）之间有没有被它整除的数，一旦有退出循环，退出循环后通过检验循环变量的值来判断是不是素数。即，当循环正常退出，循环变量的值等于n时，该数是素数；当循环提前退出，循环变量的值小于等于n-1，该数不是素数。 程序代码如下： Private Sub Command1_Click() Dim n As Integer, i As Integer n = Val(Text1.Text) If n < 1 Then MsgBox "请正确输入数据" Else n = Val(Text1.Text) For i = 2 To n - 1 If n Mod i = 0 Then Exit For Next i If i = n Then MsgBox n & "是素数" Else MsgBox n & "不是素数" End If End If End Sub 2）判断某数是否为素数。根据标志位flg来判断。 Private Sub Command1_Click() Dim n As Integer, i As Integer Dim flg As Boolean flg = True n = Val(Text1.Text) If n < 1 Then MsgBox "请正确输入数据" Else n = Val(Text1.Text) For i = 2 To n - 1 If n Mod i = 0 Then flg = False Next i If flg = True Then MsgBox n & "是素数" Else MsgBox n & "不是素数" 奇异的素数规律现象（一） 江苏省南通市崇川区张忠(言) 在对素数规律的探索中, 我发现了一些令人难以置信的奇异现象如下: 现象一现利用某一确定的规则给出模2x3x5x7的两个最小非负剩余集: B={1,29,41,47,163,169,181,209.}, Y={0,12,18,30,42,60,72,102,108,138,150,168,180,198.} 则可发现以下两种情况: 情况甲: 1) 当b-y>0时: b-y与b+y是和为偶数2b的一对模210的简化剩余(类); 2) 当b-y>1,b+y<121时: b-y与b+y是和为偶数2b的一对奇素数. 例:59-0与59+0; 59-12与59+12;...59-48与59+48 都是和为偶数2b=118的一对奇素数. 等等,等等. 情况乙: 1)当y-1>0时: y-1与y+1为模210的孪生简化剩余(类). 2)当y-1>0且y+1<121时: y-1与y+1为孪生素数.例: 12-1与12+1; 18-1与18+1; 30-1与30+1; 42-1与42+1; 60-1与60+1 72-1与72+1 102-1与102+1 108-1与108+1 都是孪生素数. 现象二现仍用上面确定的同一规则给出模2x3x5x7的两个最小非负剩余集: B={2,58,68,82,128,142152,208.}, Y={15,21,39,45,69,81,99,105.} 则可发现以下情况: 情况甲: 1) 当b-y>0时: b-y与b+y是和为偶数2b的一对模210的简化剩余(类); 2) 当b-y>1,b+y<121时: b-y与b+y是和为偶数2b的一对奇素数. 情况乙 1) 当y-1>0时: y-2与y+2为模210的相差为4的一对简化剩余(类). 2)当y-2>0且y+2<121时: y-2与y+2为一对相差为4的素数.例: 15-2与15+2; 21-2与21+2; 39-2与39+2; ...105-2与105+2. 都是相差为4的素数对. 敬请各位老师指教! ... ... (未完待续!) 1．自然数是0，1，2…… 2．素数是2，3，5……（不包括1的只能背1和它本身整除的自然数） 【1】求10000以内的所有素数。 素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。像著名的哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研，呕心沥血，但至今仍然未见分晓。 自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数。 求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。 但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。 第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不 必再用其他的数去除。 第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际 上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。 第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明： 如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。 如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。 而这是不可能的，所以，d1和d2中必有一个小于或等于√N。 基于上述分析，设计算法如下： (1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。 (2)用100以内的所有素数逐个试除的方法求出10000以内的素数。 首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A 数组中的一个单元中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。 【2】用筛法求素数。 简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的 1001害死人不偿命的(3n+1)猜想(15 分 对任何一个正整数n,如果它就是偶数,那么把它砍掉一半;如果它就是奇数,那么 把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,拼命想证明这个貌似很傻很天真的命题,结果闹得学生们无心学业,一心只证(3n+1),以至于有人说这就是一个 阴谋,卡拉兹就是在蓄意延缓美国数学界教学与科研的进展…… 我们今天的题目不就是证明卡拉兹猜想,而就是对给定的任一不超过 1000 的正整数n,简 单地数一下,需要多少步(砍几下)才能得到n=1？ 分析:输入一个正整数n进行循环,n=1循环截止,判断n,如果它就是偶数,那么把它砍掉一半;如果它就是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得 到n=1,并计算经过的次数m。 #include"stdlib、h" #include"stdio、h" int main() { int n,m; m=0; scanf_s("%d",&n); while(n!=1) { if(n%2==0) { n=n/2; } else { n=(3*n+1)/2; } m++; } printf_s("%d\n",m); system("pause"); } 1002写出这个数(20 分) 读入一个正整数n,计算其各位数字之与,用汉语拼音写出与的每一位数字。 分析:输入一个正整数n, while循环求出n的各位数字之与sum;如果sum等于0,那么就输出它的拼音”ling”;如果不等于0,输入数组b存放各位数字之与,在switch对这个数组进行判断数组b各个数的数值为多少,0对应"ling"; 1对应"yi";2:对应<"er";3对应"san";4对应"si";5对应"wu";6对应"liu";7对应"qi";8对应"ba";9对应"jiu"; 判断某个数是否素数： 1.定义为一个function函数过程 第一种方法： Function prime(ByVal x As Integer) As Boolean 注1 For i = 2 To x – 1 注2 If x Mod i = 0 Then Exit For Next i If i > x - 1 Then prime = True 注3 End Function 注1：这里注意形参前面有ByVal，不要ByVal也是可以的，为什么？ 因为在function中并未改变x的值，所以加不加ByVal都正确 注2：此句也可以这样写：For i = 2 To x/2 或 For i = 2 To sqr(x) 注3：此句也可以这样写：If i > x - 1 Then prime = True Else prime = False 思考：为什么不要Else prime = False 程序运行也是正确的 另外注意此处的条件i > x – 1的实际含义 调用的时候（调用函数时，最好不要用带call关键字的调用方法） If prime(x) then……… 第二种方法： Function prime(ByVal x As Integer) As Boolean Prime=false 注1 For i = 2 To x – 1 If x Mod i = 0 Then Exit Function注2 Next i prime = True 注3 End Function 注1 此句要不要都可以，思考为什么 注2和注3两条语句与第一种方法的区别 调用的时候 If prime(x) then……… 第三种方法： Function prime(ByVal x As Integer) As integer Prime=0 For i = 2 To x – 1 If x Mod i = 0 Then Exit Function Next i prime = 1 End Function 此方法与上述方法的区别 调用的时候 If prime(x)=1 then……… 费马小定理素数判定蒙哥马利算法(强烈推荐） 2009-11-07 12:42 费马小定理素数判定蒙哥马利算法 约定： x%y为x取模y，即x除以y所得的余数，当x 一、选择题 1．孪生素数猜想是希尔伯特在1900年提出的23个问题之一，2013华人数学家张益唐证明了孪生素数猜想是一个弱化形式，问题可以描述为：存在无穷多个素数p ，使得2p +是素数，素数对(,2)p p +称为孪生素数对，问：如果从30以内的素数组成的孪生素数对中随机抽取一对，这对孪生素数的积超过20的概率为（ ）． A ． 23 B ． 34 C ． 45 D ． 56 2．某城市2017年的空气质量状况如下表所示： 其中污染指数50T ≤时，空气质量为优；50100T <≤时，空气质量为良； 100150T <≤时，空气质量为轻微污染，该城市2017年空气质量达到良或优的概率为（ ） A ．35 B ．1180 C ．119 D ．56 3．某次战役中，狙击手A 受命射击敌机，若要击落敌机，需命中机首2次或命中机中3次或命中机尾1次，已知A 每次射击，命中机首、机中、机尾的概率分别为0.2、0.4、0.1，未命中敌机的概率为0.3，且各次射击相互独立．若A 至多射击两次，则他能击落敌机的概率为（ ） A ．0.23 B ．0.2 C ．0.16 D ．0.1 4．一道竞赛题，A ，B ，C 三人可解出的概率依次为1 2，13，14 ，若三人独立解答，则仅有1人解出的概率为（ ） A ． 1 24 B ． 1124 C ．1724 D ．1 5．随机抛掷一枚质地均匀的骰子，记正面向上的点数为a ，则函数()2 24 f x x ax =++至多有一个零点的概率为（ ） A ． 13 B ． 12 C ． 23 D ． 56 6．设两个独立事件A 和B 同时不发生的概率是p ,A 发生B 不发生与A 不发生B 发生的概率相同,则事件A 发生的概率为( ) 第1章前言 质数在研究整数的过程中占有一个很重要的地位，它被称为自然数的“建筑的基石”．虽然有很多数学家和学者致力于对它的研究，但成果并不显著，仍有许多问题有待解决．例如，哥德巴赫猜想困扰了人们几百年，有很多数学家对它进行了多年的研究但并没有得到解决．我国数学家陈景润的“陈氏理论”是迄今为止世界上关于哥德巴赫猜想研究的最好成果．这一成果给后人很大鼓舞，似乎离最后结果仅一步之遥，但仍一直无进展．梅森质数是数论研究的一项重要内容，研究梅森质数具有重大的意义，也是当今科学探索的热点和难点之一．随着现代科学技术的迅速发展，也加快了对质数的研究．运用计算机能够较快的计算某自然数是否是质数，知道在某范围内质数的分布情况．由于质数的无穷性，要想计算更大的质数仅有计算机还远远不够，还需要有更高的理论要求．同时，质数在加密和解密技术中的应用有了更高的要求，求尽可能大的质数和大数分解引起了通讯界和数学界的极大兴趣．另外，质数在奥数中也屡屡出现，技巧性非常强，可以锻炼和提高学生的思维．所以有必要对质数的相关问题进行阐述． 本文着重介绍质数相关问题，能够使读者形象、直观地目睹质数分布规律，了解有关质数问题． 首先，在质数基本知识中介绍质数的定义、性质及算术基本定理，并讨论判定质数的两个定理一个是威尔逊定理和另一个判定定理； 其次，研究质数个数问题，质数分布问题，得到质数个数有无穷多个，在某两个自然数之间大约有多少质数和两个相邻质数的间隙可以任意大等结论．还介绍用幼拉脱斯展纳筛法和质数辐射法来求从1到某自然数n之间所有的质数，进而分析质数的分布问题，并讨论它们的区别； 最后，介绍有关质数的著名问题，如费马质数是否有有限，梅森质数是否有无穷多个，什么是孪生质数，并用聚数来研究孪生质数对一些性质，哥德巴赫猜想的由来、研究意义等问题，以及它们理论的推广与应用． PS：本来没有决心把这个东西写完的，结果早上写到一半，出去吃个饭，没保存，回来手一抖直接关掉了，好不容易写了一大半了，只能重新写了，坑爹啊，但就是这个插曲，本来还没有决心的我，一下子却坚定了信念，一点要把这个东西写完。就这样开始吧 BY：Lee 下面，我们重新开始 ═══════════════════════════════════════════ 如何判断一个数是否是素数呢 ═══════════════════════════════════════════也许你会认为这是一个简单的问题，但事实上，世界上任何一个问题，都没有你想象中的那么简单1 + 1 是否等于2 ，这便是一个简单而又复杂的问题，呵呵。 突然想把这个东西换一种风格来写了，就这样扯淡扯下去吧。扯的时候文章中多少有内容来自于网络，没有侵权的意思，如果作者看到还请见谅。 ═══════════════════════════════════════════下面正式进入正题 ═══════════════════════════════════════════ 一、朴素判断素数 ═══════════════════════════════════════════1. 这种方法被誉为笨蛋的做法： 一个数去除以比它的一半还要大的数，一定除不尽的，这还用判断吗？？ 很容易发现的，这种方法判断素数，对于一个整数n，需要n-2 次判断，时间复杂度是O(n)在n非常大或者测试量很大的时候，这种笨蛋做法肯定是不可取的。 2. 改进一下下小学生的做法： 3. 再改进一下聪明的小学生的做法 对于一个小于n的整数X，如果n不能整除X,则n必定不能整除n/X。反之相同一个明显的优化，就是只要从2枚举到√n 即可。 因为在判断2的同时也判断了n/2。到√n时就把2到n-1都判断过了。 在这里，这个聪明的小学生还用了i*i <= n 来代替sqrt（n）， 这里是避免了调用函数sqrt（），其消耗时间很大， 特别是在大量数据测试的时候消耗很明显。 这个算法的时间复杂度，与最前面的笨蛋做法就好多了， 不过这里好像用sqrt()也没问题啊，，，，这个就不太清楚了。 但是做一个测试发现，如果是这样额话，每一次判断都要计算i*i， 求素数的算法及其复杂度分析2008-04-05 17:46关于搜寻一定范围内素数的算法及其复杂度分析 ——曾晓奇 关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识，在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信 对大家一定有帮助。 正如大家都知道的那样，一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)--n的开方,那么我们可以用这个性质用最直观的方法 来求出小于等于n的所有的素数。 num = 0; for(i=2; i<=n; i++) { for(j=2; j<=sqrt(i); j++) if( j%i==0 ) break; if( j>sqrt(i) ) prime[num++] = i; //这个prime[]是int型，跟下面讲的不同。 } 这就是最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n))，如果n 很小的话，这种算法（其实这是不是算法我都怀疑，没有水平。当然没 接触过程序竞赛之前我也只会这一种求n以内素数的方法。-_-~）不会耗时很多. 但是当n很大的时候，比如n=10000000时，n*sqrt(n)>30000000000,数量级相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不 出结果，这可不是我瞎掰的，想锻炼耐心的同学不妨试一试~。。。。 在程序设计竞赛中就必须要设计出一种更好的算法要求能在几秒钟甚至一秒钟之内找出n以内的所有素数。于是就有了素数筛法。 （我表达得不清楚的话不要骂我，见到我的时候扁我一顿我不说一句话。。。） 素数筛法是这样的： 1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false. 2.然后： for( i=3; i<=sqrt(n); i+=2 ) { if(prime[i]) for( j=i+i; j<=n; j+=i ) prime[j]=false; } 3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。 原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质 数的倍数筛掉。 一个简单的筛素数的过程：n=30。 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 压力式喷雾干燥塔各主要工艺 控制参素数对产品质量的影响 廖庆禄 （福建杨振华851生物科技股份有限公司，福建福州350015）摘要：通过对GNT～101型压力式喷雾干燥塔使用时各控制参素数的分析，指出喷雾过程各主要控制参素数对产品质量有着不同的影响，并探讨了他们之间的相互关系，明确了当某个参数发生变化，其它参数也应做相应调整，以及对于不同品种控制参数是不同的，应根据实验总结出不同的控制参数要求。 喷雾干燥是液体工艺成形和干燥工业中最广泛应用的工艺。最适用于从溶液、乳液、悬乳液和可泵性糊状液体原料中生成粉状、颗粒状或块状固体产品。在制药工业中，喷雾干燥常用于对中药提取浓缩液的干燥，药品生产中，通常对药粉的颗粒大小分布、残留水份含量、堆积密度和颗粒形状色泽有着不同的要求。要想达到要求就需对喷雾干燥过程各控制参数对产品质量的影响加以分析。目前所使用的喷雾干燥器主要有压力式、气流式、和离心式三种。压力式喷雾干燥器（又称喷雾干燥塔）在生产中使用最普遍。压力式喷雾干燥器的产品成微粒状，一般平均粒度可达150-200um左右，产品有良好的流动性、润湿性、润滑性等应用性能，所以深受用户的欢迎。【1】本文即以作者所在单位使用的上海乳品机械厂生产的GNT～101型压力式喷雾干燥塔为例进行探讨。 1 工作原理 本设备为立式压力喷雾干燥器，物料由高压均质泵经高压管由塔顶均风器中间喷入塔内，经喷头雾化呈70-80度雾化角的雾滴，雾滴与相对湿度很低，经过过滤和加热的再经均风器进入的热风接触，二者瞬间发生强烈的热交换和质交换；热风的热能供给雾滴使其水分蒸发，并干燥成含水分合乎要求的粉粒，蒸发出 来的水分被热风带走，通过袋过滤器由排风机排入大气。其中大部分产品落至塔体圆锥部分，由震锤震落至出粉口连续排至接粉桶（袋）。 2 工作特点 （1）干燥速度快，料液经雾化后表面积大大增加，在热风气流中，瞬间就可蒸发92%-98%的水分，完成干燥时间仅需数秒钟，特别适用于热敏性物料的干燥。该型号设备水分蒸发量为70公斤/小时。 （2）产品具有良好的均匀度、流动性和溶解性，产品纯度高，质量好。 （3）生产过程简化，操作控制方便。对于湿含量40-80%（特殊物料可达90%）的液体能一次干燥成粉粒产品，干燥后不需要粉碎和筛选，减少生产工序，提高产品纯度。对产品粒径、松密度、水份，在一定范围内可通过改变操作条件进行调整，控制和管理都很方便。 （4）适用于热敏性和非热敏性物料的干燥，适用于水溶液和有机溶剂物料的干燥，原料液可以是溶液、泥浆、乳浊液、糊状物或融熔物等均可处理。 （5）喷雾干燥的缺点主要是投资费用比较高和喷雾干燥属于对流型干燥器，热效率比较低（除非利用非常高的温度），一般为30%～40%。【2】 3 生产过程各主要控制工艺参数对产品质量的影响 喷雾干燥过程需要密切注意操作参数的变化，以便生产出符合一定要求的干燥产品。生产过程的每个阶段都能对干燥产品的性能产生一定程度的影响。如雾化方法和料液性质将确定产品的粒度分布、松密度、外观和湿含量。雾滴与空气的接触、干燥室的设计以及实际的干燥操作情况将确定产品的松密度、湿含量、易碎性、口味和活性的保持。在实际生产中，对于特定设备而言，，主要对料液中固含量、料液温度、进风温度、塔内温度、排风温度、塔内真空度、雾化压力和进料速度这几个参数进行控制。3.1 料液中固含量 问题描述：键盘输入m和n（10 一．控制流测试1、控制流图如下: 2、根据以上控制流图： 因为控制流的1-2-3-2部分为用户输入的m,n的重复赋值过程，与输入数据密切相关且每次取值不同，关系到控制流测试，所以将此独立出来：以为节点“2”的复合谓词为或的关系，全为false时只有一种情况，而为true 时有7种情况，对“2”的复合谓词（m<=10||m>=n||n>2000）为真假时其表1如下： 设A:m<=10; B:m>=n; C:n>2000 但是对于节点“2”的情况，并非所有可能都会取到，因为当A为真时，就不会执行B，依此，生成下表2： 根据表2，得出此部分的取值及路径为： 分解质因数的算法 程序源代码： #include { b[k++]=a[i]; } } for(i=0;i c[m++]=b[i]; fun1(); /*利用递归调用把每一个质因数都放入数组中*/ } } } void fun2() { printf("分解之后的因式为：\n"); printf("%d=",n); for(i=0;i for(i=0;i 数学对于计算机的重要性 可能有很多朋友在网上看过google公司早几年的招聘广告，它的第一题如下了:{first 10-digit prime found in consecutive digits e}.com，e中出现的连续的第一个10个数字组成的质数。据说当时这个试题在美国很多地铁的出站口都有大幅广告，只要正确解答了这道题，在浏览器的地址栏中输入这个答案，就可以进入下一轮的测试，整个测试过程如同一个数学迷宫，直到你成为google的一员。 又如Intel某年的一道面试题目:巴拿赫病故于1945年8月31日。他出生年份是他在世某年年龄平方减去这年年龄的差，问:他是哪年出生的?这道看似很简单的数学问题，你能不能很快地解答呢? 下面则是一道世界第一大软件公司微软的招聘测试题:中间只隔一个数字的两个素数被称为素数对，比如5和7，17和19，证明素数对之间的数字总能被6整除(假设这两个素数都大于6)，现在证明没有由三个素数组成的素数对。这样的试题还有很多很多，这些题目乍初看上去都是一些数学问题。但是世界上一些著名的公司都把它们用于招聘测试，可见它们对新员工数学基础的重视。数学试题与应用程序试题是许多大型软件公司面试中指向性最明显的一类试题，这些试题就是考察应聘者的数学能力与计算机能力。 某咨询公司的一名高级顾问曾说:微软是一家电脑软件公司，当然要求其员工有一定的计算机和数学能力，面试中自然就会考察这类能力。微软的面试题目就考察了应聘人员对基础知识的掌握程度、对基础知识的应用能力，甚至暗含了对计算机基本原理的考察。所以，这样的面试题目的确很“毒辣”，足以筛选到合适的人。 四川大学数学学院的曹广福教授曾说过:“一个大学生将来的作为与他的数学修养有很大的关系”。大学计算机专业学生都有感触，计算机专业课程中最难的几门课程莫过于离散数学、编译原理、数据结构，当然像组合数学、密码学、计算机图形学等课程也令许多人学起来相当吃力，很多自认为数据库学得很好的学生在范式、函数依赖、传递依赖等数学性比较强的概念面前感到力不从心，这些都是因为数学基础或者说数学知识的缺乏所造成的。 数学是计算机的基础，这也是为什么考计算机专业研究生数学都采用最难试题(数学一)的原因，当然这也能促使一些新的交叉学科如数学与应用软件、信息与计算科学专业等飞速发展。许多天才程序员本身就是数学尖子，众所周知，BillGates的数学成绩一直都很棒，他甚至曾经期望当一名数学教授，他的母校——湖滨中学的数学系主任弗雷福?赖特曾这样谈起过他的学生:“他能用一种最简单的方法来解决某个代数或计算机问题，他可以用数学的方法来找到一条处理问题的捷径，我教了这么多年的书，没见过像他这样天分的数学奇才。他甚至可以和我工作过多年的那些优秀数学家媲美。当然，比尔也各方面表现得都很优秀，不仅仅是数学，他的知识面非常广泛，数学仅是他众多特长之一”。影响一代中国程序人的金山软件股份有限公司董事长求伯君当年高考数学成绩满分进一步说明了问题。很多数学基础很好的人，一旦熟悉了某种计算机语言，他可以很快地理解一些算法的精髓，使之能够运用自如，并可能写出时间与空间复杂度都有明显改善的算法。 程序设计当中解决的相当一部分问题都会涉及各种各样的科学计算，这需要程序员具有什么样的基础呢?实际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。从中我们不难看出数学在程序设计领域的重要性。算法与计算理论是计算机程序设计领域的灵魂所在，是发挥程序设计者严谨，敏锐思维的有效工具，任何的程序设计语言都试图将之发挥得淋漓尽致。 程序员需要一定的数学修养，不但是编程本身的需要，同时也是培养逻辑思维以及严谨的编程作风的需要。数学可以锻炼我们的思维能力，可以帮助我们解决现实中的问题。可以帮助我们更高的学习哲学。为什么经常有人对一些科学计算程序一筹莫展，他可以读懂质数的判断
不同算法的100到999之间的素数代码
孪生素数猜想初等证明详解
求素数列表和判断素数的算法
PAT计算机能力考试乙级1-10题答案
C语言素数的几种判断方法
VB常用算法——素数
奇异的素数规律现象(一)
C语言求素数问题算法
PAT计算机能力考试乙级110题答案
判断某个数是否素数
费马小定理 素数判定 蒙哥马利算法
深圳市必修第二册第五单元《概率》测试卷(包含答案解析)
关于质数问题的讨论
素数的几种判断方法和实现
求素数的算法及其复杂度分析
压力式喷雾干燥塔各主要工艺控制参素数对产品质量的影响
素数判断程序测试范例
分解质因数的算法
数学对于计算机的重要性