-- 作者：huang01 -- 发布时间：2004-10-21 17:05:18 -- 31． 32.要发就发 “1898--要发就发”。请将不超过1993的所有素数从小到大排成第一行，第二行上的每个素数都等于它右肩上的素数之差。编程求出：第二行数中是否存在这样的若干个连续的整数，它们的和恰好是1898？假好存在的话，又有几种这样的情况？ 第一行：2 3 5 7 11 13 17......1979 1987 1993 第二行：1 2 2 4 2 4...... 8 6 *问题分析与算法设计： 首先从数学上分析该问题： 假设第一行中的素数为n[1]、n[2]、n[3]....n、...第二行中的差值为m[1]、m[2]、m[3]...m[j]...。其中m[j]为： m[j]=n[j+1]-n[j]。 则第二行连续N个数的和为： SUM=m[1]+m[2]+m[3]+...+m[j] =(n[2]-n[1])+(n[3]-n[2])+(n[4]-n[3])+...+(n[j+1]-n[j]) =n[j+1]-n[1] 由此题目就变成了：在不超过1993的所有素数中是否存在这样两个素数，它们的差恰好是1898。若存在，则第二行中必有所需整数序列，其和恰为1898，。 对等价问题的求解是比较简单的。 由分析可知，在素数序列中不必包含2，因为任意素数与2的差一定为奇数，所以不必考虑。 *程序与程序注释： #include
36
*思考题 将1,2，3，。。。,20这20个连续的自然数排成一圈，使任意两个相邻的自然数之和均为素数。 32． 35.素数幻方 求四阶的素数幻方。即在一个4X4 的矩阵中，每一个格填 入一个数字，使每一行、每一列和两条对角线上的4 个数字所组成的四位数，均为可逆素数。 *问题分析与算法设计 有了前面的基础，本题应当说是不困难的。 最简单的算法是：采用穷举法，设定4X4矩阵中每一个元素的值后，判断每一行、每一列和两条对角线上的4个数字组成的四位数是否都是可逆素数，若是则求出了满足题意的一个解。 这种算法在原理是对的，也一定可以求出满足题意的全部解。但是，按照这一思路编出的程序效率很低，在微机上几个小时也不会运行结束。这一算法致命的缺陷是：要穷举和判断的情况过多。 充分利用题目中的“每一个四位数都是可逆素数”这一条件，可以放弃对矩阵中每个元素进行的穷举的算法，先求出全部的四位可逆素数(204个)，以矩阵的行为单位，在四位可逆素数的范围内进行穷举，然后将穷举的四位整数分解为数字后，再进行列和对角线方向的条件判断，改进的算法与最初的算法相比，大大地减少了穷举的次数。 考虑矩阵的第一行和最后一行数字，它们分别是列方向四位数的第一个数字和最后一个数字，由于这些四位数也必须是可逆素数，所以矩阵的每一行和最后一行中的各个数字都不能为偶数或5。这样穷举矩阵的第一行和最后一行时，它们的取值范围是：所有位的数字均不是偶数或5的四位可逆数。由于符合这一条件的四位可逆素数很少，所以这一范围限制又一次减少了穷举的次数。 对算法的进一步研究会发现：当设定了第一和第二行的值后，就已经可以判断出当前的这种组合是否一定是错误的(尚不能肯定该组合一定是正确的)。若按列方向上的四个两位数与四位可逆数的前两位矛盾(不是其中的一种组合)，则第一、二行的取值一定是错误的。同理在设定了前三行数据后，可以立刻判断出当前的这种组合是否一定是错误的，若判断出矛盾情况，则可以立刻设置新的一组数据。这样就可以避免将四个数据全部设定好以后再进行判断所造成的低效。 根据以上分析，可以用伪语言描述以上改进的算法： 开始 找出全部四位的可逆素数； 确定全部出现在第一和最后一行的四位可逆素数； 在指定范围 内穷举第一行 在指定范围内穷举第二行 若第一、第二、三行已出现矛盾，则继续穷举下一个数； 在指定范围内穷举第四行 判断列和对角方向是否符合题意 若符合题意，则输出矩阵； 否则继续穷举下一个数； 结束 在实际编程中，采用了很多程序设计技巧，假如设置若干辅助数组，其目的就是要最大限度的提高程序的执行效率，缩短运行时间。下面的程序运行效率是比较高的。 *程序与程序注释 #include
37
int find2(void); int find0(int num); void p_array(void); void main() { int i,k,flag,cc=0,i1,i4; printf(\ for(i=1001;i<9999;i+=2) /*求满足条件的可逆素数*/ { k=i/1000; if(k%2!=0&&k!=5&&num(i)) /*若可逆素数的第一位不是偶数或5*/ { number[count][0]=i; /*存入数组*/ process(count++); /*分解素数的各位数字*/ if(number[count-1][2]%2!=0&& /*若可逆素数满足放在矩阵第一行*/ number[count-1][3]%2!=0&& /*和最后一行的条件，记录可逆素数的*/ number[count-1][2]!=5&& /*下标，计数器加1*/ number[count-1][3]!=5) select[selecount++]=count-1; } } larray[0][lcount[0]++]=number[0][0]/100; /*临时数组的第一行存前二位*/ larray[1][lcount[1]++]=number[0][0]/10; /*临时数组的第二行存前三位*/ for(i=1;i 38 } } int num(int number) /*判断是否可逆素数*/ { int j; if(!ok(number)) return 0; for(j=0;number>0;number/=10) /*将素数变为反序数*/ j=j*10+number; if(!ok(j)) return 0; /*判断反序数是否为素数*/ return 1; } int ok(int number) /*判断是否为素数*/ { int i,j; if(number%2==0) return 0; j=sqrt((double)number)+1; for(i=3;i<=j;i+=2) if(number%i==0) return 0; return 1; } void process(int i) /*将第i个整数分解为数字并存入数组*/ { int j,num; num=number[0]; for(j=4;j>=1;j--,num/=10) number[j]=num; } void copy_num(int i) /*将array[0]指向的素数的各位数字复制到array中*/ { int j; for(j=1;j<=4;j++) array[j]=number[array[0>[j]; } int comp_num(int n) /*判断array中每列的前n位是否与可逆素数允许的前n位矛盾*/ { static int ii; /*用内部静态变量保存前一次查找到的元素下标*/ static int jj; /*ii:前一次查找前二位的下标，jj:前一次查找前三位的下标*/ int i,num,k,*p; /*p:指向对应的要使用的前一次下标ii或jj*/ int *pcount; /*pcount:指向要使用的临时数组数量的计数器*/ switch(n){ /*根据n的值选择对应的一组控制变量*/ case 2:pcount=&lcount[0];p=ⅈbreak; case 3:pcount=&lcount[1];p=&jj;break; default:return 0; } for(i=1;i<=4;i++) /*对四列分别进行处理*/ { for(num=0,k=0;k 39 if(*p<0||*p>=*pcount) { *p=0; return 0; } if(num!=larray[n-2][*p]) return 0; /*前n位不是可逆素数允许的值则返回0*/ } return 1; } int find1(int i) /*判断列方向是否是可逆素数*/ { int num,j; for(num=0,j=0;j<4;j++) num=num*10+array[j]; return find0(num); } int find2(void) /*判断对角线方向是否是可逆素数*/ { int num1,num2,i,j; for(num1=0,j=0;j<4;j++) num1=num1*10+array[j][j+1]; for(num2=0,j=0,i=4;j<4;j++,i--) num2=num2*10+array[j]; if(find0(num1)) return(find0(num2)); else return 0; } int find0(int num) /*查找是否为满足要求的可逆素数*/ { static int j; if(num<=number[j][0])for(;j>=0&&num