内容发布更新时间 : 2025/2/9 7:16:11星期一 下面是文章的全部内容请认真阅读。

C++语言程序百例精解

C/C++语言经典、实用、趣味程序设计编程百例精解（4）

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("d=%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 ? "=:%d" : "=:%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; }

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; }

*思考题