哥德巴赫猜想 ——— 极限算法（你要是能写出比我用时还短的代码算我输）
程序员文章站
2022-03-18 11:13:06
...
哥德巴赫猜想
哥德巴赫猜想概述：
任何一个≥6之偶数，都可以表示成两个奇质数之和
那么，接下来，我们就来研究研究哥德巴赫猜想的验证及优化方案:
第一步，先建立头文件 “mec.h”（建立头文件的目的：简化程序，使程序更加直观，编写更加方便，在查找错误以及修改程序时，更加方便）：
#ifndef _MEC_H_
#define _MEC_H_
typedef unsigned char boolean
#define TRUE 1
#define FALSE 0
#endif
这里解释一下这个头文件的内容：用C语言编译器来实现java中数据类型boolean，这种类型的函数主要是用来辨别的，即：判断是否满足一些要求，满足，则返回值为TRUE，不满足，则返回值为FALSE。
第二步，开始编写主函数（伪代码版本）：
#include <stdio.h> //因为头文件<stdio.h>中所涉及函数太广泛，所以可以上手就将其写上
int main() {
int maxNum;
int i;
printf("请输入一个范围：");
scanf("%d", &maxNum);
for(i=6; i<maxNum; i+=2) {
if(不满足歌德巴赫猜想) {
printf("%d！！！！！！！该数字不满足哥德巴赫猜想！！！！！！！！\n", i);
return 0;
}
}
printf("哥德巴赫猜想毫无问题！\n");
return 0;
}
第三部，编写主函数所需函数伪代码：
boolean isGoldbach(int num) {
int i;
if(num%2) {
return FALSE;
} //除二以外的偶数都是非质数，而歌德巴赫猜想验证的是大于6的数字
for(i=3; i<=num; i+=2) {
if(i是质数 && （num-i）也是质数) {
return TRUE;
}
}
return FALSE;
}
因为，可以看出：这个函数还需要一个“判断是否为质数”的函数，
所以，编写“判断质数”的函数：
boolean isPrime(int num) {
int i;
int borderNumber=(int)sqrt(num); //根据数学知识：边界数值最小是总数的算术平方根 ,但是，sqrt()函数需要<math.h>头文件
if(num%2==0 && num>2) {
return FALSE;
}
for(i=3; i <= borderNumber && num%i; i++)
;
return i>borderNumber;
}
于是，由以上代码可以得到初步goldbach.c的代码：
#include <stdio.h>
#include <math.h>
#include "./include/mec.h"
boolean isPrime(int num); //判断是否是质数
boolean isGoldbach(int num); //判断该数是否满足歌德巴赫猜想
boolean isGoldbach(int num) {
int i;
if (num % 2) {
return FALSE;
}
for (i = 3; i <= num / 2; i += 2) {
if (isPrime(i) && isPrime(num - i)) {
// printf("%d = %d + %d\n", num, i, num - i);
return TRUE;
}
}
return FALSE;
}
boolean isPrime(int num) {
int i;
int borderNumber = (int) sqrt(num);
if (num % 2 == 0 && num > 2) {
return FALSE;
}
for (i = 3; i <= borderNumber && num % i; i++)
;
return i > borderNumber;
}
int main() {
int maxNum;
int i;
printf("请输入一个范围:");
scanf("%d", &maxNum);
for (i = 6; i < maxNum; i += 2) {
if (!isGoldbach(i)) {
printf("%d！！！！！！！该数字不满足哥德巴赫猜想！！！！！！！！\n", i);
return 0;
}
}
printf("哥德巴赫猜想完全成立！\n");
return 0;
}
emmm,你是不是觉得，这就完了？我很搞笑吗？这么烂的代码往上放？
哦哦，你是不是还没看出来这段代码的弊端呢？
哈哈，上面的话开个玩笑，接下来，来解释上述代码的缺点：
大家可以先想想，如果按照上面代码来运行的话，从第一个数到最大范围中的每个数都要判断是否是质数，而如果范围较大，判断是否为质数的操作也会耗费很长时间。
正所谓，眼见为实，那么让我用我这台古老的机子来看看一下8位数内验证歌德巴赫猜想所要消耗多长时间吧：
对代码做些调整：
#include <stdio.h>
#include <time.h>
#include <math.h>
#include "./include/mec.h"
boolean isPrime(int num);
boolean isGoldbach(int num);
boolean isGoldbach(int num) {
int i;
if (num % 2) {
return FALSE;
}
for (i = 3; i <= num / 2; i += 2) {
if (isPrime(i) && isPrime(num - i)) {
// printf("%d = %d + %d\n", num, i, num - i);
return TRUE;
}
}
return FALSE;
}
boolean isPrime(int num) {
int i;
int borderNumber = (int) sqrt(num);
if (num % 2 == 0 && num > 2) {
return FALSE;
}
for (i = 3; i <= borderNumber && num % i; i++)
;
return i > borderNumber;
}
int main() {
int maxNum;
int i;
long startTime;
long endTime;
long deltaTime;
printf("请输入一个范围:");
scanf("%d", &maxNum);
startTime = clock();
for (i = 6; i < maxNum; i += 2) {
if (!isGoldbach(i)) {
printf("%d !发现错误，我们验证出了不满足哥德巴赫猜想的数！\n", i);
return 0;
}
}
endTime = clock();
deltaTime = endTime - startTime;
printf("耗时:%ld.%03lds\n", deltaTime / CLOCKS_PER_SEC, deltaTime % CLOCKS_PER_SEC);
printf("哥德巴赫猜想完全正确！\n");
return 0;
}
运行这段代码后，输入八位数（10000000），结果如下：
为了缩短运行时间，我们知道，位运算所消耗时间最短，而遍历“只存素数”数组查找素数能极大地缩短时间，于是，我们大胆对代码改动为如下版本：
头文件：
#ifndef _MEC_H_
#define _MEC_H_
typedef unsigned char boolean;
#define TRUE 1
#define FALSE 0
#define SET(v, i) (v |= (1 << ((i) ^ 7))) //将二进制数v中的第i位改为1
#define CLR(v, i) (v &= ~(1 << ((i) ^ 7))) //将二进制数v中的第i位改为0
#define GET(v, i) (((v) & (1 << ((i) ^ 7))) != 0) //读取二进制数v中的第i位
#endif
goldbach.c :
#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include "./include/mec.h"
boolean *numberPool; //因为不知道范围大小，为了避免空间的浪费，等下用<malloc.h>头文件中的函数申请堆空间
boolean isPrime(int num);
boolean isGoldbach(int num);
boolean *screenPrime(int count);
boolean *screenPrime(int count) {
int i;
int j;
boolean *num;
num = (boolean *) calloc(sizeof(u8), (count + 7) >> 3); //用动态存储方式，可减少空间的浪费，并且，用calloc申请的空间，初始值都是0
for (i = 4; i < count; i += 2) { //除二以外所有偶数均为非质数
SET(num[i >> 3], i & 7); //用1表示非质数，用0表示质数
}
for (i = 3; i*i <= count; i += 2) {
if (GET(num[i >> 3], i & 7) == 0) {
for (j = i*i; j < count; j += i) {
SET(num[j >> 3], j & 7);
}
}
}
return num;
}
boolean isGoldbach(int num) {
int i;
for (i = 3; i <= num / 2; i += 2) {
if (isPrime(i) && isPrime(num - i)) {
return TRUE;
}
}
return FALSE;
}
boolean isPrime(int num) {
return GET(numberPool[num >> 3], num & 0x07) == 0; //这一步的目的是用二进制中该数对应的相应位的数值判断是否为质数
}
int main() {
int maxNum;
int i;
long startTime;
long endTime;
long deltaTime;
printf("请输入范围:");
scanf("%d", &maxNum);
numberPool = screenPrime(maxNum);
startTime = clock();
for (i = 6; i < maxNum; i += 2) {
if (!isGoldbach(i)) {
printf("%d！！！！！！！该数字不满足哥德巴赫猜想！！！！！！！！\n", i);
return 0;
}
}
endTime = clock();
deltaTime = endTime - startTime;
printf("耗时:%ld.%03lds\n", deltaTime / CLOCKS_PER_SEC, deltaTime % CLOCKS_PER_SEC);
printf(" 哥德巴赫猜想完全正确！\n");
free(numberPool); //申请“堆”空间后，一定要记得释放，以免造成“内存泄漏”
return 0;
}
这里稍稍解释下上端代码运用的数学知识：
歌德巴赫猜想的欧拉验证方法： 质数的倍数一定是非质数。
所以上述代码将质数的倍数都从质数的数组中剔除（即二进制相应位的数改为1）
运行后，输入八位数（即10000000）结果为如下：
由此可以看出，合理应用二进制的知识和数组，虽然在空间复杂度上偏高，但是，相对地，时间复杂度会极大地降低。
本人初次写博客，可能所学知识浅薄，语言表达不清楚，亦或是语言冗杂，如果读者朋友们有意见或者建议，欢迎提出，谢谢 ！！！
上一篇： jquery怎么判断对象是否是数组