哥德巴赫猜想验证-创新互联

1、问题描述

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

 例：12 = 3 + 9 X

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

基本分析

2、基础算法代码实现

#include

typedef unsigned char boolean;

#define TRUE    1
#define    FALSE    0

boolean isPrime(int n);
boolean Gguess(int userNumber);

boolean Gguess(int userNumber){
    int num;
    int i;
    int flag = 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);
            }
        }
    }
}

boolean isPrime(int n){
    int i;

    for(i = 2; i= n;
}

void main(void){
    int num;

    printf("请输入一个边界数: ");
    scanf("%d", &num);

    if(FALSE == Gguess(num)){
        printf("哥德巴赫猜想失败\n");
    }else{
        printf("哥德巴赫猜想成功了\n");
    }
}

结果截图

算法分析：

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

3、中级算法

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

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

算法模型：

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

#include
#include
#include

void findPrime(int number, char **p);

void findPrime(int number, char **p){
    int len = (int)(sqrt(number));
    int i;
    int j;
    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;
}

void main(void){
    int number;
    char *p = NULL;
    int i; 

    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
#include
#include

//位运算计算的效率更快
#define        SET_BIT(byte, i)    (byte |= 1 << (7 ^ (i)))  //设置这个字节的指定位为1
#define        CLR_BIT(byte, i)    (byte &= ~(1 << (7 ^ (i)))) //设置这个字节的指定位为0
#define        GET_BIT(byte, i)    !!((byte) & (1 << (7^(i))))  //得到这个字节的指定位

// num >> 3  数组下标
// num & 7 <===> num % 8  
void findPrime(int number, char **p);

void findPrime(int number, char **p){
    int len = (int)(sqrt(number));
    int i;
    int j;
    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;
}

void main(void){
    int number;
    char *p = NULL;
    int i; 

    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
#include
#include

typedef unsigned char boolean;

#define    TRUE    1
#define FALSE    0

//位运算计算的效率更快
#define        SET_BIT(byte, i)    (byte |= 1 << (7 ^ (i)))  //设置这个字节的指定位为1
#define        CLR_BIT(byte, i)    (byte &= ~(1 << (7 ^ (i)))) //设置这个字节的指定位为0
#define        GET_BIT(byte, i)    !!((byte) & (1 << (7^(i))))  //得到这个字节的指定位

// num >> 3  数组下标
// num & 7 <===> num % 8  
void findPrime(int number, char **p);
boolean isPrime(int num, char *p);
boolean Gguess(int userNumber, char *p);

boolean Gguess(int userNumber, char *p){
    int num;
    int i;
    int flag = 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);
            }
        }
    }

    return flag;
}

boolean isPrime(int num, char *p){
    return GET_BIT(p[num >> 3], num & 7) == 0;  //0：表示为质数;
}

void findPrime(int number, char **p){
    int len = (int)(sqrt(number));
    int i;
    int j;
    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;
}

void main(void){
    int num;
    char *p;

    printf("请输入一个边界数: ");
    scanf("%d", &num);

    findPrime(num, &p);
    if(FALSE == Gguess(num, p)){
        printf("哥德巴赫猜想失败\n");
    }else{
        printf("哥德巴赫猜想成功了\n");
    }
}

结果截图：

算法分析：

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

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。