1、问题描述

大于等于6以上的偶数总有 = 2个质数之和；

例：12 = 3 + 9 X

12 = 5 + 7 V (哥德巴赫猜想成立)；

基本分析

2、基础算法代码实现

#include<stdio.h>typedefunsignedcharboolean;#defineTRUE1#defineFALSE0booleanisPrime(intn);booleanGguess(intuserNumber);booleanGguess(intuserNumber){intnum;inti;intflag=TRUE;for(num=6;TRUE==flag&&num<userNumber;num+=2){//从6开始---userNumber的所有数字进行哥德巴赫猜想flag=FALSE;for(i=3;i<num&&FALSE==flag;i+=2){if(isPrime(i)&&isPrime(num-i)){flag=TRUE;printf("%d=%d+%d\n",num,i,num-i);}}}}booleanisPrime(intn){inti;for(i=2;i<n&&n%i;i++);returni>=n;}voidmain(void){intnum;printf("请输入一个边界数:");scanf("%d",&num);if(FALSE==Gguess(num)){printf("哥德巴赫猜想失败\n");}else{printf("哥德巴赫猜想成功了\n");}}

结果截图

算法分析：

基础算法，的真正耗时的主要运算在"质数判断"上，无需计算，算法速度将大大加快。

3、中级算法

(1)、思路：先把9位以内的所有质数都找出来，是质数的为0，不是质数的为1，判断是否为质数查表即可；

筛选法：以数组下标为数值本身，而相关元素的值为0或1，0：是质数，1：非质数；

算法模型：

(2)、判断是否为质数的高效代码

#include<stdio.h>#include<math.h>#include<malloc.h>voidfindPrime(intnumber,char**p);voidfindPrime(intnumber,char**p){intlen=(int)(sqrt(number));inti;intj;char*pool;pool=(char*)calloc(sizeof(char),number);for(i=2;i<len;i++){//从2判断到根号number的长度即可if(pool[i]==0){for(j=i*i;j<number;j+=i){//前面的都重复的判断过了pool[j]=1;//非质数标记为1}}}*p=pool;}voidmain(void){intnumber;char*p=NULL;inti;printf("请输入多少位内的质数:");scanf("%d",&number);findPrime(number,&p);for(i=3;i<number;i++){if(p[i]==0){printf("%d",i);}}printf("\n");free(p);}

(3)、结果截图

算法分析：

因为用的辅助空间是char类型的，而只需存储0/1，所有太浪费内存空间，并且都是* 、/这类，运算速度比较慢

4、极端算法

(1)、位运算的判断质数

#include<stdio.h>#include<math.h>#include<malloc.h>//位运算计算的效率更快#defineSET_BIT(byte,i)(byte|=1<<(7^(i)))//设置这个字节的指定位为1#defineCLR_BIT(byte,i)(byte&=~(1<<(7^(i))))//设置这个字节的指定位为0#defineGET_BIT(byte,i)!!((byte)&(1<<(7^(i))))//得到这个字节的指定位//num>>3数组下标//num&7<===>num%8voidfindPrime(intnumber,char**p);voidfindPrime(intnumber,char**p){intlen=(int)(sqrt(number));inti;intj;char*pool;pool=(char*)calloc(sizeof(char),(number+7)>>3);for(i=2;i<len;i++){//从2判断到根号number的长度即可if(GET_BIT(pool[i>>3],i&7)==0){for(j=i*i;j<number;j+=i){//前面的都重复的判断过了SET_BIT(pool[j>>3],j&7);//非质数标记为1}}}*p=pool;}voidmain(void){intnumber;char*p=NULL;inti;printf("请输入多少位内的质数:");scanf("%d",&number);findPrime(number,&p);for(i=3;i<number;i++){if(GET_BIT(p[i>>3],i&7)==0){printf("%d",i);}}printf("\n");free(p);}

(2)、哥德巴赫猜想的完整算法

#include<stdio.h>#include<math.h>#include<malloc.h>typedefunsignedcharboolean;#defineTRUE1#defineFALSE0//位运算计算的效率更快#defineSET_BIT(byte,i)(byte|=1<<(7^(i)))//设置这个字节的指定位为1#defineCLR_BIT(byte,i)(byte&=~(1<<(7^(i))))//设置这个字节的指定位为0#defineGET_BIT(byte,i)!!((byte)&(1<<(7^(i))))//得到这个字节的指定位//num>>3数组下标//num&7<===>num%8voidfindPrime(intnumber,char**p);booleanisPrime(intnum,char*p);booleanGguess(intuserNumber,char*p);booleanGguess(intuserNumber,char*p){intnum;inti;intflag=TRUE;for(num=6;TRUE==flag&&num<userNumber;num+=2){//从6开始---userNumber的所有数字进行哥德巴赫猜想flag=FALSE;for(i=3;i<num&&FALSE==flag;i+=2){if(isPrime(i,p)&&isPrime(num-i,p)){flag=TRUE;printf("%d=%d+%d\n",num,i,num-i);}}}returnflag;}booleanisPrime(intnum,char*p){returnGET_BIT(p[num>>3],num&7)==0;//0：表示为质数;}voidfindPrime(intnumber,char**p){intlen=(int)(sqrt(number));inti;intj;char*pool;pool=(char*)calloc(sizeof(char),(number+7)>>3);for(i=2;i<len;i++){//从2判断到根号number的长度即可if(GET_BIT(pool[i>>3],i&7)==0){for(j=i*i;j<number;j+=i){//前面的都重复的判断过了SET_BIT(pool[j>>3],j&7);//非质数标记为1}}}*p=pool;}voidmain(void){intnum;char*p;printf("请输入一个边界数:");scanf("%d",&num);findPrime(num,&p);if(FALSE==Gguess(num,p)){printf("哥德巴赫猜想失败\n");}else{printf("哥德巴赫猜想成功了\n");}}

结果截图：

算法分析：

关键在质数判断上面进行的算法的极简优化，由char-->位的简化，和位运算的执行速率极高；