优化哥德巴赫猜想的算法

原帖在此处

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void create_prime (char *s, int **prime, int n, int *prime_len) {
    int i, j, _len, max;
    int *_prime;

    max=(int)sqrt((double)n);
    while (max * max <= n)
        max++;
    max--;


    /* 初始化s数组,全部写零 */
    for (i=0; i<n; i++)    s[i] = 0;

    /*
    除1以外的数都分为质数和合数
    除2以外的偶数都是合数, 质数只可能存在于奇数中
    所以把3到sqrt(n)之内的质数求出
    (如果n是合数, 必然有一个约数是大于1而小于等于它的平方根)
    该奇数的倍数都是合数,打上标记1.剩下的奇数则都为质数.
    比如36的平方根为6, 那么除3和5的倍数以外的奇数则都为质数(也包含了1和2).
    */

    //从3开始遍历到max的奇数
    for (i=3; i<=max; i+=2)
        if(s[i] == 0)
            //从6开始,把质数的倍数标记为1(它们都是合数)
            for(j=i*i; j<=n; j+=i*2)
                s[j]=1;

    *prime_len = 0;
    _len = 10000;
    if ((_prime = malloc(sizeof(int) * _len)) == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(1);
    }
    for (i=3; i<=n; i+=2) {//把所有质数存入数组
        if (s[i] == 0) { //如果是质数
            if (*prime_len >= _len) { //判断动态内存是否足够
                _len += 10000;
                _prime = realloc(_prime, sizeof(int) * _len);
            }
            _prime[*prime_len] = i;
            *prime_len += 1; //prime_len为质数的数量
        }
    }
    *prime = _prime;
}

int check (char *s, int *prime, int n, int prime_len) {
    int i, j, flag;

    //遍历所有大于2的偶数
    //因为哥德巴赫猜想是求大于2的偶数
    for (i=4; i<=n; i+=2) {
        flag = 0;
        //j < prime_len 保证不越界超过质数的数量范围
        //i > prime[j] 确保相减不是一个负数
        for (j=0; j<prime_len && i>prime[j]; j++) {
            //从我们的质数表prime[0]开始
            //如果i - prime[j]也是一个质数,则偶数i就是两个质数的和
            //哥德巴赫猜想成立
            if (s[i-prime[j]] == 0) {
                flag = 1;
                break;
            }
        }
        if(flag == 0)    return -1;
    }

    return 0;
}

int main(int argc, char **argv) {
    int n, prime_len;
    int *prime;
    char *s;

    time_t t = time(NULL);
    if (argc < 2) {
        printf("Please type the range\n");
        exit(-1);
    }
    n = atoi(argv[1]);
    if((s = (char *)malloc(n)) == NULL) {
        fprintf(stderr, "malloc failed\n");
        return 1;
    }

    create_prime(s, &prime, n, &prime_len);

    if(check(s, prime, n, prime_len) == 0)
        t = time(NULL) - t;
        printf("in the range 4 - %d, Goldbach conjecture was established.\nit takes %ld seconds.\n", n, t);

    return 0;
}

不足之处欢迎拍砖, 感谢cjaizss.

本程序利用的筛法, 申请两块内存区域, 一个状态机, 一个质数表, 指针s指向的内存区域为n个字节, 初始化为0, 把0到n个数种的合数筛选出来, 在数组s中设置为1, 再求出状态机为0的即为质数(包括1和2,非合数也非质数), 存放进数组prime中, 遍历检查的时候, 就用偶数n减去质数表内的质数, 把结果放入状态机中看是否值为0, 如果为0那么也是一个质数, 则哥德巴赫猜想成立, 跳出循环, 检查下一个偶数.