c.txt

C语言经典的一些程序

一个数k(如n=13，则a=169且k=961)，若a等于k则可判定n为回亠数。

*程序说明与注释

原程序好像有错，而且比较费解，现基于原程序修改如下（如果读者还发现错误请提出）： 

#include<stdio.h>
int main(void)
{
int m[16],n,i,t,count=0;
long unsigned a,k;
printf("No. number it's square(palindrome)\n");
for(n=1;n<256;n++) /*穷举n的取值范围*/
{
k=0;t=1;a=n*n; /*计算n的平方*/

for(i=0;a!=0;i++) /*从低到高分解数a的每一位存于数组m[0]~m[16]*/
{
m=a%10;//这个是取得a的个位，整个循环合起来就可以取得各个位
a/=10; 
}

int j=0;
for(i–;j<i;j++,i–)//因为n的平方的各个位都存在数组中了，下面判断是不是对称
if(m[j]!=m)break;//只要有一位不是对称，那就说明不是对称，就可以退出了

//所有的位都对称就说明是对称了，这样就可以打印出结果了
if(j>=i)printf("%2d%10d%10d\n",++count,n,n*n);

} 

return 0;
}

*运行结果
No. number it's square(palindrome)
1 1 1
2 2 4
3 3 9
4 11 121
5 22 484
6 26 676
7 101 10201
8 111 12321
9 121 14641
10 202 40804
11 212 44944

//下面程序是原来的，有错，而且费解
#include<stdio.h>
int main(void)
{
int m[16],n,i,t,count=0;
long unsigned a,k;
printf("No. number it's square(palindrome)\n");
for(n=1;n<256;n++) /*穷举n的取值范围*/
{
k=0;t=1;a=n*n; /*计算n的平方*/

for(i=1;a!=0;i++) /*从低到高分解数a的每一位存于数组m[1]~m[16]*/
{
m=a%10;//安安注：这个是取得a的个位，整个循环合起来就可以取得各个位,并存于数组中，为了是下

面判断是不是对称
a/=10; 
}

for(;i>1;i–)
{
k+=m[i-1]*t;
t*=10;
}
if(k==n*n)
printf("%2d%10d%10d\n",++count,n,n*n);
} 

return 0;
}


*运行结果
No. number it's square(palindrome)
1 1 1
2 2 4
3 3 9
4 11 121
5 22 484
6 26 676
7 101 10201
8 111 12321
9 121 14641

29.求具有abcd=(ab+cd)2性质的四位数

3025这个数具有一种独特的性质：将它平分为二段，即30和25，使之相加后求平方，即(30+25)2，恰好等

于3025本身。请求出具有这样性质的全部四位数。

*问题分析与算法设计
具有这种性质的四位数没有分布规律，可以采用穷举法，对所有四位数进行判断，从而筛选出符合这种性

质的四位数。具体算法实现，可任取一个四位数，将其截为两部分，前两位为a，后两位为b，然后套用公

式计算并判断。

*程序说明与注释
#include<stdio.h>
int main()
{
int n,a,b;
printf("There are following number with 4 digits satisfied condition\n");
for(n=1000;n<10000;n++) /*四位数N的取值范围1000~9999*/
{
a=n/100; /*截取N的前两位数存于a*/
b=n%100; /*截取N的后两位存于b*/
if((a+b)*(a+b)==n) /*判断N是否为符合题目所规定的性质的四位数*/
printf("%d ",n);
}
}

*运行结果
There are following numbers with 4 digits satisfied condition:
2025 3025 9801 

30.求素数

求素数表中1~1000之间的所有素数

*问题分析与算法设计
素数就是仅能衩1和它自身整除的整数。判定一个整数n是否为素数就是要判定整数n能否被除1和它自身之

外的任意整数整除，若都不能整除，则n为素数。
程序设计时i可以从2开始，到该整数n的1/2为止，用i依次去除需要判定的整数，只要存在可以整除该数

的情况，即可确定要判断的整数不是素数，否则是素数。

*程序说明与注释
#include<stdio.h>
int main()
{
int n1,nm,i,j,flag,count=0;
do{
printf("Input START and END=?");
scanf("%d%d",&n1,&nm); /*输入求素数的范围*/
}while(!(n1>0&&n1<nm)); /*输入正确的范围*/
printf("………..PRIME TABLE(%d–%d)…………\n",n1,nm);
if(n1==1||n1==2) /*处理素数2*/
{
printf("%4d",2);
n1=3;count++;
}
for(i=n1;i<=nm;i++) /*判定指定范围内的整数是否为素数*/
{
if(!(i%2))continue;
for(flag=1,j=3;flag&&j<i/2;j+=2)
/*判定能否被从3到整数的一半中的某一数所整除*/
if(!(i%j))flag=0; /*若能整除则不是素数*/
if(flag) printf(++count%15?"%4d":"%4d\n",i);
}
}

*思考题
请找出十个最小的连续自然数，它们个个都是合数(非素数)


31.歌德巴赫猜想


验证：2000以内的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对2000以内的正偶数成立)。

*问题分析与算法设计
为了验证歌德巴赫猜想对2000以内的正偶数都是成立的，要将整数分解为两部分，然后判断出分解出的两

个整数是否均为素数。若是，则满足题意；否则重新进行分解和判断。
程序中对判断是否为素数的算法进行了改进，对整数判断“用从2开始到该整数的一半”改为“2开始到该

整数的平方根”。原因何在请自行分析。

*程序说明与注释
#include<stdio.h>
#include<math.h>
int fflag(int n);
int main()
{
int i,n;
for(i=4;i<=2000;i+=2)
{
for(n=2;n<i;n++) /*将偶数i分解为两个整数*/
if(fflag(n)) /*分别判断两个整数是否均为素数*/
if(fflag(i-n))
{
printf("%14d=%d+%d\n",i,n,i-n); /*若均是素数则输出*/
break;
}
if(n==i) printf("error %d\n",i);
}
}

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; /*if yes,return 1*/
} 


32.可逆素数 

求四位的可逆素数。可逆素数指：一个素数将其各位数字的顺序倒过来构成的反序数也是素数。

*问题分析与算法设计
　　本题的重点不是判断素数的方法，而是求一个整数的反序数。求反序数的方法是从整数的末尾依次截

取最后一位数字，每截取一次后整数缩小10倍，将截取的数字作为新的整数的最后一位（新的整数扩大10

倍后加上被截取的数字）。这样原来的整数的数字从低到高被不断地截取，依次作为新的整数从高到低的

各位数字。 

*程序说明与注释
#include<stdio.h>
#include<math.h>
int num(int number);
int ok(int number);
int main()
{
int i,count;
printf("There are invertable primes with 4 digits: \n");
for(count=0,i=1001;i<9999;i+=2) //穷举全部的奇数
{
if(num(i)) //若是可逆素数，则输出
printf(count%9 ? "%3d:%d" : "%3d:%d\n",++count,i);
}
return 0;
} 

int num(int number)
{
int i,j;
if(!ok(number))return 0; //判断是否为素数
for(i=number,j=0;i>0;i/=10) //按位将整数倒过来，产生反序数
{
j=j*10 + i%10;
}
if(number<j) //若原数小于反序数
{
if(!ok(i)) //判断对应的反序数是否为可逆素数
{
return 0;
}
else
{
return 1; //若是可逆数素数，则返回1
}
}
else
{
return 0; 
}
getchar();
return 0;
}

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) //若为素数则返回1，否则返回0
return 0;
}

return 1;
}

*思考题

求1000以内的孪生素数。孪生素数是指：若a为素数，且a+2也是素数，则素数a和a+2称为孪生素数。

33.回文素数

求不超过1000的回文素数。

*问题分析与算法设计
　　所谓回文素数是指，对一个整数n从左向右和从由向左读其结果值相同且是素数，即称n为回文素数。

所以本题的重点不是判断素数的方法，而是求回文整数。构造回文数的方法很多，这里仅介绍一种最简单

的算法。实现思路是先求出一个整数的回文数，再判断是否为素数。
　　不超过1000的回文数包括二位和三位的回文数，我们采用穷举法来构造一个整数并求与其对应的反序

数，若整数与其反序数相等，则该整数是回文数。

*程序说明与注释
#include<stdio.h> 

int a(int n)
int main()
{
int i,j,t,k,s;
printf("Following are palindrome primes not greater than 1000:\n");
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("%d\t",s);
}
}
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、…第二行中的差值为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<stdio.h>
#include<math.h>
#define NUM 320
int number[NUM]; /*存放不超过1993的全部奇数*/
int fflag(int i);
int main()
{
int i,j,count=0;
printf("there are follwing primes sequences in first row:\n");
for(j=0,i=3;i<=1993;i+=2) /*求出不超过1993的全部奇数*/
if(fflag(i)) number[j++]=i;