在有限范围内证明哥德巴赫猜想成立

原帖:

在此感谢《品悟C》的作者:pmerofc, 我只做了一些注释的修改.


前几天看到一篇关于哥德巴赫猜想的文章，才知道哥德巴赫猜想的真正含义：

任何一个大于2的偶数，都可以表示成两个质数的和。

这就是所谓的哥德巴赫猜想的“1+1”，比如12=5+7，而陈景润先生证明的“1+2”，实际上是“一个足够大的偶数，可以表示成或者两个质数的和，或者一个质数（用1表示）加上两个质数的积（用2表示）”，比如100＝23＋7X11。
这篇文章解开了自己长久以来关于哥德巴赫猜想的一个误解。当时突发奇想，哥德巴赫猜想要求的是任何一个大于2的偶数都。。。，这种句式，不是跟《C程序设计伴侣》中所介绍的适用于for循环结构的句式有点类似吗？哥德巴赫猜想虽然没有终点，但是它有一个起点（4，最小的大于2的偶数），他要求每个大于2的偶数都。。。，这也就是它的循环变化条件（偶数，每次循环加2，检查下一个偶数），只要我们添加一个循环终点，就构成了一个完整的for循环结构，也就可以用程序验证在这个范围内的所有偶数是不是都符合哥德巴赫猜想，如果所有偶数都符合，也就是说，在这个范围内，我们找不到一个反例，这就意味着我们在有限范围内用程序逐个验证的方法证明了哥德巴赫猜想成立。
按照上面的分析，我们可以很容易地实现这个想法：

// glodbach.c 在有限范围内证明哥德巴赫猜想成立
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>

// 判断某个数是不是质数
static bool isprime(unsigned int n)
{
    // 0和1不是质数
    if(0==n || 1==n) return false;
    // 直接返回2和3是质数
    if(2==n || 3==n) return true;
    // 对这个数开平方
    // 如果一个正整数n是合数, 必然有一个约数是大于1而小于等于它的平方根
    // 这样只需要找出一个正整数大于1而小于等于它的平方根,然后又可以被它整除
    // 那么这个数就不会是质数
    double end = sqrt(n);
    // 试图找出一个约数可以被它自己整除
    for(int i=2;i<end;++i) {
        if(n%i) { // 如果有余数，不能整除
            continue; // 继续判断下一个
        }
        // 如果找到n可以被i整除，这n不是质数
        return false;
    }
    // 所有从2到end的数都无法整除，则是质数
    return true;
}
// 判断数字n是否符合哥德巴赫猜想
static bool goldbach(unsigned int n)
{
    // 保证是一个大于2的偶数
    if(0 != n%2 || n<=2) return false;
    // 取得中点
    unsigned int mid = n/2;
    // 从2循环到中点
    for(unsigned int i = 2;i<=mid;++i) {
        // 将n分解成i和n-i，
        // 如果i和n-i都是质数，即哥德巴赫猜想成立
        if(isprime(i)&&isprime(n-i)) {
            return true;
        }
    }
    // 无法将n表示成两个质数的和，哥德巴赫猜想不成立
    return false;
}

int main() {
    bool e = true; // 假设哥德巴赫猜想成立
    unsigned int begin = 4;
    unsigned int end = 50000000; // 人为设定终点
    // 计时开始
    time_t t = time(NULL);
    // 利用for循环，
    // 在begin和end之间寻找反例
    for(unsigned int n = begin;n<=end;n+=2) {
        // 如果找到反例
        if(!goldbach(n)) {
            // 则哥德巴赫猜想不成立
            // 如果在此范围内找不到一个反例，则成立
            e = false;
            break;
        }
    }
    // 计算耗时
    t = time(NULL) - t;
    // 输出结果
    if(e) {
        printf("in the range %d - %d, Goldbach conjecture was established.\nit takes %ld seconds.\n",
            begin,end,t);
    }
    return 0;
}

编译命令: gcc goldbach.c -std=c99 -lm