位运算应用：哥德巴赫猜想九位数以内的验证---算法优化
位运算应用：哥德巴赫猜想九位数以内的验证
哥德巴赫猜想是所有大于4的偶数都能被分解为2个质数之和。即，每个大于4的偶数只需分解出一个质数之和的形式就说明该偶数符合哥德巴赫猜想；若一个大于4的偶数始终不能被分解为两个质数之和的形式，则哥德巴赫猜想失败。
接下来我将先提出基本框架，再在基本框架的基础上进行代码优化，降低代码时间复杂度。
基本思路为：
1.判断一个大于4的偶数是否符合哥德巴赫猜想，并试图将其分解成两个质数之和。
2.进行质数的判断。
3.在九位数以内验证哥德巴赫猜想。
基本框架代码如下：
#include <stdio.h>
#include <time.h>
#include "mec.h"
boolean isGuessRight(int num);
boolean isPrime(int num);
void Goldbachbase(int maxNum);
void Goldbachbase(int maxNum) {
int i;
for(i = 6;i < maxNum;i += 2) {
if(!isGuessRight(i)) {
printf("%d使哥德巴赫猜想失败！\n",i);
}
}
printf("哥德巴赫猜想成功！\n");
}
boolean isPrime(int num) {
int i;
for(i = 2;i < num && num % i;i++) {
}
return i >= num;
}
boolean isGuessRight(int num) {
int i;
for(i = 3;i <= num/2;i += 2) {
if(isPrime(i) && isPrime(num - i)) {
return TRUE;
}
}
return FALSE;
}
int main() {
int maxNum;
long starTime;
long endTime;
printf("Input the maxNum:");
scanf("%d",&maxNum);
starTime = clock();
Goldbachbase(maxNum);
endTime = clock() - starTime;
printf("哥德巴赫猜想耗时：%d.%03ds\n",endTime / 1000,endTime % 1000);
return 0;
}
输入：1000000
输出：
哥德巴赫猜想成功！
哥德巴赫猜想耗时：1025.651s
此代码虽然可以完成哥德巴赫猜想的验证，但是耗时过长！只进行了1000000以内的验证就已经花费了17分钟，若想验证9位数以内所耗时间可想而知！
观察代码发现，isPrime函数被调用了两次，而且内部存在非常多的循环和取余运算，这是该代码中最耗时的部分，进行进一步优化！
解决isPrime函数内部循环次数过多问题：
i 需要一直增加到 num - 1吗？
思考：若num为120；判断120是否为质数；
i= 2时：120 / 2 = 60； 那么61到119就没有必要再验证了，因为120除以61到119中的某个数，商一定在1到2之间，但1到2之间不存在能被120整除的数。
i= 3时：120 / 3 = 40；那么41到119就没有必要再验证了，因为i在41到119之间逐渐扩大的同时，商在1到3之间逐渐缩小，3之前的整数都验证过了。以此类推……
i= 10时：120 / 10 = 12；13到119就没有必要再验证了，因为1到10都验证过了。若是再验证13到119就重复验证，会做很多无谓的循环判断。所以，i只需要增加到120的算术平方根取整即可。
结论：i只需增加到num的算术平方根，即，判断一个数是否为质数，只需要除以2到它的算术平方根就可判断出它是否为质数！
isPrime函数代码优化后：
boolean isPrime(int num) {
int i;
int range =(int)sqrt(num) + 1;
if(2 == num) {
return TRUE;
}
if(0 == num % 2) {
return FALSE;
}
for(i = 3;i < range && num % i;i++) {
}
return i >= range;
}
输入：1000000
输出：
哥德巴赫猜想成功！
哥德巴赫猜想耗时：1.291ss
这样使循环次数大大减小，1000000以内的验证耗时直接变为1.291s.接下来解决取余运算过多问题：
若是能将推导一个数是否为质数变为直接判断一个数是否为质数，将省去大量的取余运算。
思路：现在用动态分配存储空间创建一个一维数组，数组元素此时皆为0，表示该数为质数，若该数为非质数则将该元素的值变为1；元素下标即为所对应的数值。最后验证哥德巴赫猜想时，直接在数组中查即可。
关键点是
1.由于验证九位数以内的数，则所占内存空间将非常大，这是用空间换时间；但是也要尽可能地减少内存空间，所以用unsigned char类型，即boolean类型(在mec.h中有相关宏定义，mec.h将在最后给出)
2.标识质数，用筛选法将非质数筛除掉，手工过程如下：
增加了一个制造质数数组函数并且修改了isPrime函数，代码如下：
#include <stdio.h>
#include <time.h>
#include <malloc.h>
#include "mec.h"
boolean *primePool = NULL;
boolean isGuessRight(int num);
boolean isPrime(int num);
void Goldbachbase(int maxNum);
void makePrime(int maxNum);
void makePrime(int maxNum) {
int i;
int j;
primePool = (boolean *)calloc(sizeof(boolean),maxNum);
for(i = 4;i < maxNum;i += 2) {
primePool[i] = 1;
}
for(i = 3;i*i < maxNum;i += 2) {
if(0 == primePool[i]) {
for(j = i*i;j < maxNum;j += i) {
primePool[j] = 1;
}
}
}
}
void Goldbachbase(int maxNum) {
int i;
for(i = 6;i < maxNum;i += 2) {
if(!isGuessRight(i)) {
printf("%d使哥德巴赫猜想失败！\n",i);
}
}
printf("哥德巴赫猜想成功！\n");
}
boolean isPrime(int num) {
return 0 == primePool[num];
}
boolean isGuessRight(int num) {
int i;
for(i = 3;i <= num/2;i += 2) {
if(isPrime(i) && isPrime(num - i)) {
return TRUE;
}
}
return FALSE;
}
int main() {
int maxNum;
long starTime;
long endTime;
long midTime;
long miT;
printf("Input the maxNum:");
scanf("%d",&maxNum);
starTime = clock();
makePrime(maxNum);
midTime = clock();
Goldbachbase(maxNum);
endTime = clock() - midTime;
miT = midTime - starTime;
printf("制造质数耗时：%d.%03d 哥德巴赫猜想耗时：%d.%03ds\n",
miT / 1000,miT % 1000,endTime / 1000,endTime % 1000);
free(primePool);
return 0;
}
输入：1000000000
输出：
哥德巴赫猜想成功！
制造质数耗时：16.562s 哥德巴赫猜想耗时：53.609s
惊喜嘛？！！！九位数以内的哥德巴赫猜想才用了53.609s,还记得最开始的平滑方式用了多少秒吗？！
但是为了验证九位数以内的哥德巴赫猜想申请了1GB的空间，而且用8位二进制位表示0或1太奢侈！仅使用了1/8的空间，空间利用率低！所以，将制造质数函数进一步优化。
若是能用一个二进制位表示0或1，即，一个字节表示8个数值，所占空间将缩小为原来的8倍！空间利用率提高！
关键点：
1.数值与数组元素中的每一位二进制位如何对应，即num对应第x字节第y位
x = num / 8 = num >> 3
y = num%8 = num & 7
位运算速度更快，所以采用位运算!
2.数组需要申请多大空间：
如：想要表示32需要5个字节；表示55需要7个字节；所以，想要表示num，需要num/8 + 1个字节！
用到三个有关位运算的宏，在我的上一篇博文位运算及诸技巧中有详解：
#define SET(num,i) ((num) | (1 << ((i) ^ 7)))
#define DLR(num,i) ((num) & ~(1 <<((i) ^ 7)))
#define GET(num,i) (((num) >> ((i) ^ 7)) & 1)
只需要修改makePrime()函数和isPrime()函数即可.
代码如下：
makePrime()函数:
void makePrime(int maxNum);
void makePrime(int maxNum) {
int i;
int j;
primePool = (boolean *)calloc(sizeof(boolean),(maxNum >> 3) + 1);
for(i = 4;i < maxNum;i += 2) {
primePool[i >> 3] = SET(primePool[i >> 3],i & 7);
}
for(i = 3;i*i < maxNum;i += 2) {
if(0 == GET(primePool[i >> 3],i & 7)) {
for(j = i*i;j < maxNum;j += i) {
primePool[j >> 3] = SET(primePool[j >> 3],j & 7);
}
}
}
}
isPrime()函数:
boolean isPrime(int num);
boolean isPrime(int num) {
return 0 == GET(primePool[num >> 3],num & 7);
}
输入：1000000000
输出：
哥德巴赫猜想成功！
制造质数耗时：18.255s 哥德巴赫猜想耗时：72.413s
程序优化完毕，比上一次优化后的程序，时间慢了20s左右，但空间却缩小了8倍，虽然是用时间换空间，但还是非常值得的！
该项目依赖于头文件mec.h的支持，如下：
#ifndef _MEC_H_
#define _MEC_H_
typedef unsigned char boolean;
typedef boolean u8;
typedef unsigned short u16;
typedef unsigned int u32;
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1
#define SET(num,i) ((num)|(1<<((i)^7)))
#define DLR(num,i) ((num)& ~(1<<((i)^7)))
#define GET(num,i) (((num)>>((i)^7))&1)
int skipBlank(const char *str);
#endif