哥德巴赫猜想的验证
一、什么是哥德巴赫猜想
哥德巴赫猜想：任意大于6的偶数，都可以分解为两个质数的和。
二、哥德巴赫猜想的验证
方法一：
#include <stdio.h>
#include <time.h>
#include "mec.h"
void checkGoldBech(int num);
boolean canResolve(int num);
boolean isPrime(int num);
boolean isPrime(int num){
int n;
for(n = 2;n < num && num % n;n ++ ){
;
}
return n >= num;
}
boolean canResolve(int num){
int j;
for(j = 3;j <= num/2 ;j += 2){
if(isPrime(j) && isPrime(num - j)){
// printf("%d = %d + %d\n",num ,j ,num - j);
return TRUE;
}
}
return FALSE;
}
void checkGoldBech(int num){
int i;
for(i = 6;i <= num; i += 2){
if(!canResolve(i)){
printf("哥德巴赫猜想是错误的！！\n");
return;
}
}
printf("哥德巴赫猜想是正确的！！！\n");
}
int main(){
int num;
long startTime;
long endTime;
printf("请输入要查询的范围：");
scanf("%d",&num);
startTime = clock();
checkGoldBech(num);
endTime = clock();
endTime -= startTime;
printf("耗时：%d.%03d\n",endTime / 1000,endTime % 1000);
return 0;
}上述的方法，在判断一个数是否为质数的函数（isPrime）中，使用了大家最容易想到的操作：即n从0开始循环与num相与，直至n循环到num-1。而恰恰是这个函数最为耗时，使得程序的效率极低。当运行程序时，验证的位数较大（8位数或者更大）时，耗时极多。因此，我们有必要对此函数进行优化！！
方法二：
boolean isPrime(int num){
int n;
int midleNum;
if(n == 2){
return TRUE;
}
if(num % 2 == 0 && num >2){
return FALSE;
}
midleNum = (int)(sqrt(num) + 1);
for(n = 3;n <= midleNum && num % n;n += 2 ){
;
}
return n > midleNum;
}方法二在方法一的基础上，更优化了一步。当传入一个num时，先判断是否为2，若是2(质数)，直接返回TRUE；若是其它数，先排除所有大于2偶数，然后再对奇数进行判断。在这里，循环只需要进行到根号下num即可。理由如下：若传入的数为10000，10000/2 = 5000，则从5001到9999之间，不会存在一个数可以被10000整除;再思考，10000/3 = 3333.33，那么，3333到4999之间就没必要考虑了;10000 / 4 = 2500，那么，2501到 3332之间就不用考虑了...... 并且，如果我们检测过了2，那就没有必要再检测5000了。综上，对于10000，我们只需要从2检测到100就够了，也就是检测到根号10000就够了，
方法三：
程序再优化：不再对2至根号num的数进行意义判断，而是直接“得知”这个数是否为质数，这样就可以极大地提高算法的速度！
若要求验证的范围为num，则，将[2，num)中所有的质数全部找到，并把它们存放在一个拥有num个元素的数组中。假设index在[2，num)之间，以index为下标，array[index]中的值有两种：0或1，分别代表质数和非质数。
这样一来，判断一个数是否为质数，只需要判断array[index]中的值即可！
boolean *primePool; //质数池（数组）
void screenPrime(int count){
int prime = 2;
int i;
int lastNum;
int index;
for(index = 4;index < count ;index += 2){
primePool[index] = 1;
}
lastNum = (int(sqrt(count)) + 1);
for(index = 3;index <= lastNum ; index += 2){
if(primePool[index] == 0){
for(i = index * index;i < count;i += index){
primePool[i] = 1;
}
}
}
} //筛选质数并设置0/1
boolean isPrime(int num){
return !primePool[num]; //判断数组元素中的值
}在上面的筛选质数函数（screenPrime）中,我们对质数的判断又进行了优化。这里要提出一种方法：筛选法。
以上的解释摘自百度百科。
在这里对筛选法再进行一些解释，若一个数m是质数，则2*m已经被2筛去了，3*m已经被3筛去了...... 因此从m*m开始筛选即可！相信上述定义对照来看代码不难理解。
方法四：
方法三仍有优化的地方，它最大的消耗是内存空间！因为需要申请一个长度为num的数组！虽然我们已经使用了boolean 类型，但还是耗费了很多空间。那么，我们是否可以用一个二进制位来表示一个数是否为质数呢？答案是可以。
通过上图我们可以清晰地看到从数组的第一个元素开始，依次保存0~num的质数性（每个元素保存八个数字的质数性）。这样一来，就大大地节省了内存空间。
下面，我们只需要宏定义三个量，分别进行“取位”、“清位”、“置位”的操作即可。
#define SETB(value,index) (value |= 1 << ((index)^7)) //置位
#define CLRB(value,index) (value &= ~(1 << ((index)^7))) //清位
#define GETB(value,index) (((value) & (1 <<((index) ^ 7))) != 0) //取位有了这三个宏定义，我们进一步的代码优化就可以完成了：
void screenPrime(int count){
int prime = 2;
unsigned int i;
unsigned int j;
int lastNum;
int index;
for(index = 4;index < count ;index += 2){
SETB(primePool[index >> 3],index & 7);
}
lastNum = (int(sqrt(count)) + 1);
for(i = 3;i <= lastNum ; i += 2){
if(!GETB(primePool[(unsigned int) i >> 3],i & 7)){
for(j = i * i;j < count;j += i){
SETB(primePool[j >> 3],j & 7);
}
}
}
}在这种方法中，我们使用了位运算，即对“位”来进行操作。这是计算及内部极其高效的一种手段，因而也极大地提高了程序的效率！！
以上说法若有不周之处，还请各位指点。