{
if(number %i ==0) //若为素数则返回1，否则返回0 return 0; } return 1; } *思考题
求1000以内的孪生素数。孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2称为孪生素数。 33.回文素数
求不超过1000的回文素数。 *问题分析与算法设计
所谓回文素数是指，对一个整数n从左向右和从由向左读其结果值相同且是素数，即称n为回文素数。所以本题的重点不是判断素数的方法，而是求回文整数。构造回文数的方法很多，这里仅介绍一种最简单的算法。实现思路是先求出一个整数的回文数，再判断是否为素数。 不超过1000的回文数包括二位和三位的回文数，我们采用穷举法来构造一个整数并求与其对应的反序数，若整数与其反序数相等，则该整数是回文数。 *程序说明与注释 #include
int i,j,t,k,s;
printf(\for(i=0;i<=9;++i) //穷举第一位 for(j=0;j<=9;++j) //穷举第二位 for(k=0;k<=9;++k) //穷举第三位 {
s=i*100 + j*10 + k; //计算组成的整数 t=ik*100 + j*10 + i; //计算对应的反序数
if(i == 0 && j==0) //处理整数的前两位为0的情况 { t/100; }
else if(i ==0) //处理整数的第一位为0的情况 { t/10; }
if(s.10 && s==t && a(s)) //若大于10且为回文素数，则输出 {
printf(\
} } return 0; }
//判断参数n是否为素数 int a(int n) { int i;
for(i=2;i<(n-1)/2;+=i) {
if(n%i == 0) return 0; } return 1; }
*运行结果
Following are palindrome primes not greater than 1000: 11 101 131 151 181 191 313 353 373 383 727 787 797 919 929 *思考题
优化生成回文数的算法。 34.要发就发
―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[i]、…第二行中的差值为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
int number[NUM]; /*存放不超过1993的全部奇数*/ int fflag(int i); int main() {
int i,j,count=0;
printf(\for(j=0,i=3;i<=1993;i+=2) /*求出不超过1993的全部奇数*/ if(fflag(i)) number[j++]=i;
for(j–;number[j]>1898;j–) /*从最大的素数开始向1898搜索*/ {
for(i=0;number[j]-number[i]>1898;i++); /*循环查找满足条件的素数*/ if(number[j]-number[i]==1898) /*若两个素数的差为1898，则输出*/ printf(\\\n\} }
int fflag(int i) { int j;
if(i<=1) return 0; /*判断是否为素数*/ if(i==2) return 1;
if(!(i%2)) return 0; /*if no, return 0*/ for(j=3;j<=(int)(sqrt((double)i)+1);j+=2) if(!(i%j)) return 0; return 1; }
*运行结果
There are follwing primes sequences in first row: (1).89,……,1987 (2).53,……,1951 (3). 3,……,1901 *思考题
将1,2，3，。。。,20这20个连续的自然数排成一圈，使任意两个相邻的自然数之和均为素数。 35.素数幻方
求四阶的素数幻方。即在一个4X4 的矩阵中，每一个格填 入一个数字，使每一行、每一列和两条对角线上的4 个数字所组成的四位数，均为可逆素数。 *问题分析与算法设计
有了前面的基础，本题应当说是不困难的。
最简单的算法是：采用穷举法，设定4X4矩阵中每一个元素的值后，判断每一行、每一列和两条对角线上的4个数字组成的四位数是否都是可逆素数，若是则求出了满足题意的一个解。 这种算法在原理是对的，也一定可以求出满足题意的全部解。但是，按照这一思路编出的程序效率很低，在微机上几个小时也不会运行结束。这一算法致命的缺陷是：要穷举和判断的情况过多。 充分利用题目中的―每一个四位数都是可逆素数‖这一条件，可以放弃对矩阵中每个元素进行的穷举的算法，先求出全部的四位可逆素数(204个)，以矩阵的行为单位，在四位可逆素数的范围内进行穷举，然后将穷举的四位整数分解为数字后，再进行列和对角线方向的条件判断，改进的算法与最初的算法相比，大大地减少了穷举的次数。
考虑矩阵的第一行和最后一行数字，它们分别是列方向四位数的第一个数字和最后一个数字，由于这些四位数也必须是可逆素数，所以矩阵的每一行和最后一行中的各个数字都不能为偶数或5。这样穷举矩阵的第一行和最后一行时，它们的取值范围是：所有位的数字均不是偶数或5的四位可逆数。由于符合这一条件的四位可逆素数很少，所以这一范围限制又一次减少了穷举的次数。
对算法的进一步研究会发现：当设定了第一和第二行的值后，就已经可以判断出当前的这种组合是否一定是错误的(尚不能肯定该组合一定是正确的)。若按列方向上的四个两位数与四位可逆数的前两位矛盾(不是其中的一种组合)，则第一、二行的取值一定是错误的。同理在设定了前三行数据后，可以立刻判断出当前的这种组合是否一定是错误的，若判断出矛盾情况，则可以立刻设置新的一组数据。这样就可以避免将四个数据全部设定好以后再进行判断所造成的低效。 根据以上分析，可以用伪语言描述以上改进的算法： 开始
找出全部四位的可逆素数；
确定全部出现在第一和最后一行的四位可逆素数； 在指定范围 内穷举第一行 在指定范围内穷举第二行
若第一、第二、三行已出现矛盾，则继续穷举下一个数； 在指定范围内穷举第四行 判断列和对角方向是否符合题意 若符合题意，则输出矩阵； 否则继续穷举下一个数； 结束
在实际编程中，采用了很多程序设计技巧，假如设置若干辅助数组，其目的就是要最大限度的提高程序的执行效率，缩短运行时间。下面的程序运行效率是比较高的。 *程序说明与注释 #include
int number[210][5]; /*存放可逆素数及素数分解后的各位数字*/ int select[110]; /*可以放在矩阵第一行和最后一行的素数的下标*/ int array[4][5]; /*4X4的矩阵，每行0号元素存可逆素数对应的数组下标*/ int count; /*可逆素数的数目*/
int selecount; /*可以放在矩阵第一行和最后一行的可逆素数的数目*/
int larray[2][200]; /*存放素数前二、三位数的临时数组所对应的数量计数器*/ int lcount[2];
int num(int number); int ok(int number); void process(int i); void copy_num(int i); int comp_num(int n); int find1(int i); int find2(void); int find0(int num); void p_array(void); int 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 if(larray[0][lcount[0]-1]!=number[i][0]/100) larray[0][lcount[0]++]=number[i][0]/100; if(larray[1][lcount[1]-1]!=number[i][0]/10) larray[1][lcount[1]++]=number[i][0]/10; } for(i1=0;i1 array[0][0]=select[i1]; /*取对应的素数下标*/ copy_num(0); /*复制分解的素数*/ for(array[1][0]=0;array[1][0]