偶然在CSDN上看到 类 哥德巴赫 猜想的程序：

C语言每日一练——第52天：一个偶数总能表示为两个素数之和_Super辉sir的博客-CSDN博客C语言每日一练 2021年11月3日——分析：虽然用C语言证明这个猜想我做不到，但我可以设定一个范围，证明范围内的数满足这个条件即可。思路：三层循环，第一层遍历所有大于2的偶数（给定的范围），第二层遍历第一个素数加数，第三层遍历第二个素数加数，当满足所有偶数都有两个素加数（为素数的加数）时，方可证明在该数字范围内，一个偶数总能表示为两个素数之和。https://blog.csdn.net/weixin_43772810/article/details/121129617感觉有点意思，就自己尝试写了一下，因为好久没有写C语言，稍微饶了点弯路，不过也算写出来了，就发出来献个丑。代码风格啥的就忽略吧，随手一写。测试了一些数据，感觉性能还行。

4-100万所有偶数，41秒；

99万到100万，1万的数据量，不到1秒。

先发结果，代码附后。

jie@Jies-MacBook-Pro test1 % ./a.out  
your input: 4 - 1000000
程序运行时长：41373.597 ms
jie@Jies-MacBook-Pro test1 % ./a.out  
your input: 990000 - 1000000
程序运行时长：927.436 ms

算法思路就两条：

1. 磨刀不误砍柴工

        无论如何，素数的计算不能重跑，那干脆一次性跑足够多的放那儿备用，从实际情况来看，百万级别数字以下的素数计算还是很快的；

2. 加和算法

        采取了两头逼近的算法，min=2，max=最接近输入数字的素数，大一个小一个无所谓。以168为例。

第一轮：min=2，max=167，加和大于168，maxIndex-1

第二轮：min=2，max=163，加和小于168，minIndex+1

第三轮：min=3，max=163，加和小于168，minIndex+1

第四轮：min=5，max=163，加和=168，成功。 

另外理论上还有优化的空间，因为这么多数的计算都是独立的，各个数字之间没有相互影响，理论上可以用上多核计算的方式。必要的情况下可以根据实际场景选择。

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

typedef int BOOL;
#define TRUE 1
#define FALSE 0

#define MAX_PRIME_LENGTH 1000000
long _primes[MAX_PRIME_LENGTH];

void calcPrimes(long max);
int isPrime(long x);
long findSmallerPrimeIndex(long number);
int divideNumber(long number, long* x, long* y);

int main()
{
    double start = clock();

    long min = 990000;
    long max = 1000000;
    printf("your input: %ld - %ld\n", min, max);

    calcPrimes(max*2);
    
    for(long i=min; i<=max; i+=2){
        long x=0, y=0;
        divideNumber(i, &x, &y);
        //printf("%ld = %ld + % ld\n", i, _primes[x], _primes[y]);
    }

    double end = clock();
    printf("程序运行时长：%.3f ms\n",(double)(end-start)/1000); //打印运行时间

    return 0;
}


// 将一个数字分割为两个素数之和
int divideNumber(long number, long* x, long* y){
    // 从两头一起开始，小于number的最大的数开始
    long maxPrimeIndex = findSmallerPrimeIndex(number);
    //printf("maxPrimeIndex = %ld\n", maxPrimeIndex);
    long indexX = 0;
    long indexY = maxPrimeIndex;

    // *x 往右，*y往左
    while(indexX < indexY)
    {
        //printf("min = %ld, max = %ld\n", _primes[indexX], _primes[indexY]);
        long r = _primes[indexX] + _primes[indexY];
        if(r < number){
            indexX++;
        } else if(r > number){
            indexY--;
        }else{
            *x = indexX;
            *y = indexY;
            return 0;
        }
    }
    return -1;

}

// 找到最接近number并且小于number的素数（这个地方可能有点bug，找到的不一定是小于的，有可能是大于的，但对性能几乎无影响）
long findSmallerPrimeIndex(long number){
    long i=0;
    for(i=0; _primes[i]<=number; i++);

    return i;
}

// 计算小于max的所有素数
void calcPrimes(long max){
    long index = 0;
    for(long i=0; i<MAX_PRIME_LENGTH; i++){
        _primes[i] = 0;
    }
    for(long i=2; i<max; i++){
        if(isPrime(i) == TRUE){
            _primes[index++] = i;
        }
    }
}

// 判断是否为素数
BOOL isPrime(long x){
    // 只要能被_primes里的内容整除，就算失败
    for(long i=0; _primes[i]<=sqrt(x); i++){
        long m = _primes[i];
        if(x % m == 0){
            return FALSE;
        }
    }
    return TRUE;
}