【C语言】->哥德巴赫猜想验证->筛选法->算法极限优化之你不可能比我快

Ⅰ 哥德巴赫猜想

哥德巴赫1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的偶数都可写成两个质数之和。但是哥德巴赫自己无法证明它，于是就写信请教赫赫有名的大数学家欧拉帮忙证明，但是一直到死，欧拉也无法证明。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数都可写成两个质数之和。今日常见的猜想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。
今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。

简单来说就是，任何一个大于2的偶数都可以分解成两个素数。

这篇博客会分四个层次，将一个普通代码优化到极限。

Ⅱ 最低级算法

哥德巴赫猜想的验证由三个部分组成：判断质数，判断偶数是否可以分解成两个质数，最后判断一个范围内哥德巴赫猜想是否正确。
以下为最简单最基础的代码，同时也是优化空间最大的????

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

#define TRUE   1
#define FALSE  0

typedef unsigned char boolean;

boolean isPrime(int num);
boolean resolve(int num);
void inspect(int ceiling);

void inspect(int ceiling) {
	int i;

	for (i = 4; i <= ceiling; i += 2) {
		if (!resolve(i)) {
			printf("哥德巴赫猜想被证伪了!\n");
			return;
		}
	}
	printf("哥德巴赫果然很厉害!\n");	
}

boolean resolve(int num) {
	int i;

	if (isPrime(num - 2)) {
		return TRUE;
	}
	for (i = 3; i <= num / 2; i += 2) {
		if (isPrime(i) && isPrime(num - i)) {
			return TRUE;
		}
	}
	return FALSE;
}

boolean isPrime(int num) {
	int i;

	for (i = 2; i < num && num % i; i++) {
		;
	}
	return i >= num;
}

int main() {
	int ceiling;
	long startTime;
	long endTime;

	printf("请输入验证哥德巴赫猜想的最大数:");
	scanf("%d", &ceiling);

	startTime = clock();
	inspect(ceiling);
	endTime = clock();

	endTime -= startTime;

	printf("消耗时间:%d.%03ds", endTime / 1000, endTime % 1000);
	printf("\n");

	return 0;
}

测试结果如下，我们要验证100 000以下的偶数是否成立????

可以看到，100 000以下的数耗时5.991秒，我们再验证1 000 000的????

可以看到，我的小破电脑居然用了这么久才验证成功，即使只是增了一个0。正经人谁会等一个程序运行这么长时间啊，所以我们要逐步将其优化，将程序优化至一个正常人可以忍受的程度。

Ⅲ 没那么低级算法-> 质数判断算法优化

在最低级的代码中，我们判断质数用的是以下的代码????

boolean isPrime(int num) {
	int i;

	for (i = 2; i < num && num % i; i++) {
		;
	}
	return i >= num;
}

尽管已经足够简单，但其仍要进行一个很大的循环，每次分解一个数时都要做两次这样的循环，很浪费时间，所以第一层优化，我们先减少查询质数的循环所消耗的时间。
我之前的循环，要让i = 2一直判断到num - 1，从这里面来判断num是否有因子将其整除，我以120为例子，提供一个新的视角。

120 / 2 = 60，这说明从61到119，没有一个数能被120整除了。
120 / 3 = 40，这说明从41到119，仅有一个数能被120整除。
……
120 / 12 = 10，那么从10以后，就没有必要验证是否有数能被120整除。

所以，只需要从i = 2,判断至sqrt(num) + 1,就可以判断出这个数到底有没有因子能被其整除了，这样，我们的每层循环就可以相较之前，少了一个平方级的数量。同样，我们也可以先通过判断这个数是否为偶数，先将偶数筛掉。
代码如下????

boolean isPrime(int num) {
	int i;
	int point;

	if (2 == num) {
		return TRUE;
	}
	if (num % 2 == 0 && num > 2) {
		return FALSE;
	}
	point = (int) (sqrt(num) + 1);

	for (i = 2; i < point && num % i; i++) {
		;
	}
	return i >= point;
}

我只修改了判断质数这一个函数，其他的仍保持不变。当最大数为100 000时，结果如下????

当最大数为1 000 000时，结果如下????

第一个代码我验证1 000 000的代码耗费了60多秒，这已经是质的提升了。好奇的我又尝试了10 000 000，结果如下????

甚至10 000 000也只是第一个代码一百万的六分之一左右，这就是减少无意义循环的意义。但我的脚步停下来了吗？不可能的，即使质数的判断已经简化了这么多，但我仍可以将其变得更简单更省时间。

Ⅳ 脱离了低级趣味的算法->筛选法->质数判断极致优化

上一个程序我判断质数仍然是在一个循环里，每验证一个数是不是符合哥德巴赫猜想，仍要调用两次循环，现在再优化，我将只使用一次循环，不用次次都调用。如何实现呢？就是用空间换时间。我先生成一个质数池，大小为从0到需要验证的最大数字，不是质数将其标注为1，这样在判断质数时，仅取质数池里的值就可以知道了。
以下代码为质数池的生成????

void creatPrimePool(int ceiling) {
	int i;
	int index;
	int point = (int) (sqrt(ceiling) + 1);

	primePool = (boolean *) calloc(sizeof(boolean), ceiling);

	for (i = 4; i < ceiling; i += 2) {
		primePool[i] = 1;
	}

	for (i = 3; i < point; i += 2) {
		if (0 == primePool[i]) {
			for (index = i * i; index < ceiling; index += i) {
				primePool[index] = 1;
			}
		}
	}
}

这个质数池的实现利用了calloc()函数的特性，申请空间会将其值置为零。这样质数的判断就很简单了????

boolean isPrime(int num) {
	return !primePool[num];
}

以下为完整代码????

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

#define TRUE   1
#define FALSE  0

typedef unsigned char boolean;

boolean *primePool;

boolean isPrime(int num);
boolean resolve(int num);
void inspect(int ceiling);
void creatPrimePool(int ceiling);

void creatPrimePool(int ceiling) {
	int i;
	int index;
	int point = (int) (sqrt(ceiling) + 1);

	primePool = (boolean *) calloc(sizeof(boolean), ceiling);

	for (i = 4; i < ceiling; i += 2) {
		primePool[i] = 1;
	}

	for (i = 3; i < point; i += 2) {
		if (0 == primePool[i]) {
			for (index = i * i; index < ceiling; index += i) {
				primePool[index] = 1;
			}
		}
	}
}

void inspect(int ceiling) {
	int i;

	for (i = 4; i <= ceiling; i += 2) {
		if (!resolve(i)) {
			printf("哥德巴赫猜想被证伪了!\n");
			printf("%d\n", i);
			return;
		}
	}
	printf("哥德巴赫果然很厉害!\n");	
}

boolean resolve(int num) {
	int i;

	if (isPrime(num - 2)) {
		return TRUE;
	}
	for (i = 3; i <= num / 2; i += 2) {
		if (isPrime(i) && isPrime(num - i)) {
			return TRUE;
		}
	}
	return FALSE;

}

boolean isPrime(int num) {
	return !primePool[num];
}

int main() {
	int ceiling;
	long startTime;
	long creatTime;
	long endTime;

	printf("请输入验证哥德巴赫猜想的最大数:");
	scanf("%d", &ceiling);

	startTime = clock();
	creatPrimePool(ceiling);
	creatTime = clock();
	inspect(ceiling);
	endTime = clock();

	endTime -= startTime;
	creatTime -= startTime;

	printf("生成质数池时间:%d.%03ds\n", creatTime / 1000, creatTime % 1000);
	printf("消耗时间:%d.%03ds", endTime / 1000, endTime % 1000);
	printf("\n");

	return 0;
}

我增加了一个生成质数池的时间，可以观察到这两个函数的运行情况。以下为运行结果????

可以看到，进行10 000 000的验证仅需要0.335秒，而上一个程序需要12秒，这又是一次质的飞跃。但我的脚步不会停下来，下一个程序我要追求极致的优化，这个程序虽然快，但是极其的浪费空间，尽管我们用的是unsigned char，但最大数是一千万，我们仍需要一千万字节的内存空间。所以下一个程序，就是空间和时间的极致优化。

Ⅴ 完美代码->你能比我还快吗

上一个程序我判断是否为质数，取的是一个boolean类型的1或0，所以为了节省空间，我不再一个字节存放一个值，而是一个位存放一个值，这样一下子就可以节省八倍的空间。如果存储八个数，只需要一个字节就够了。
要怎么实现呢？就是厉害的位运算啦。具体讲解可以看我上一篇博客。
【C语言】->位运算详细解析->位运算的使用
我对位运算有一个详尽的分析。以下为我的头文件的代码，也就是tyz.h，里面有我需要用到的类型定义以及位运算的宏。????

#ifndef _TYZ_H_
#define _TYZ_H_

#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1

#define SET(value, index)    (value |= 1 << (index ^ 7))
#define CLEAR(value, index)  (value &= ~(1 << (index ^ 7)))
#define GET(value, index)    ((value) & (1 << (index ^ 7)) != 0)

typedef unsigned char boolean;

int skipBlank(const char *str);
boolean isRealStart(int ch);


#endif

所以代码不需要改变太多，只用将值设为1的部分改成置位运算就可以了。需要注意的是，要判断一个数该存放的位置，有两个运算：

SET(primePool[i >> 3], i & 7);

i >> 3,就相当于i / 8，这样就可定位到其应存的字节；
i & 7，这个大家可以自行验证，通过与运算，即可定位到i应在的位上。
所以质数判断的代码如下????

void creatPrimePool(int ceiling) {
	unsigned int i;
	unsigned int index;
	int point = (int) (sqrt(ceiling) + 1);

	primePool = (boolean *) calloc(sizeof(boolean), (ceiling + 7) >> 3);

	for (i = 4; i < ceiling; i += 2) {
		SET(primePool[i >> 3], i & 7);
	}

	for (i = 3; i < point; i += 2) {
		if (!GET(primePool[i >> 3], i & 7)) {
			for (index = i * i; index < ceiling; index += i) {
				SET(primePool[index >> 3], index & 7);
			}
		}
	}
}

boolean isPrime(int num) {
	return !primePool[num >> 3], num & 7;
}

测试结果如下????

可以看到一千万的验证，从0.3秒降到了0.07，又是将近十倍的提速，并且所占用的空间更小。走到这一步，我们的算法优化才是到了尽头。

完整代码如下????

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

#include "tyz.h"

boolean *primePool;

boolean isPrime(int num);
boolean resolve(int num);
void inspect(int ceiling);
void creatPrimePool(int ceiling);

void creatPrimePool(int ceiling) {
	unsigned int i;
	unsigned int index;
	int point = (int) (sqrt(ceiling) + 1);

	primePool = (boolean *) calloc(sizeof(boolean), (ceiling + 7) >> 3);

	for (i = 4; i < ceiling; i += 2) {
		SET(primePool[i >> 3], i & 7);
	}

	for (i = 3; i < point; i += 2) {
		if (!GET(primePool[i >> 3], i & 7)) {
			for (index = i * i; index < ceiling; index += i) {
				SET(primePool[index >> 3], index & 7);
			}
		}
	}
}

void inspect(int ceiling) {
	int i;

	for (i = 4; i <= ceiling; i += 2) {
		if (!resolve(i)) {
			printf("哥德巴赫猜想被证伪了!\n");
			printf("%d\n", i);
			return;
		}
	}
	printf("哥德巴赫果然很厉害!\n");	
}

boolean resolve(int num) {
	int i;

	if (isPrime(num - 2)) {
		return TRUE;
	}
	for (i = 3; i <= num / 2; i += 2) {
		if (isPrime(i) && isPrime(num - i)) {
			return TRUE;
		}
	}
	return FALSE;

}

boolean isPrime(int num) {
	return !primePool[num >> 3], num & 7;
}

int main() {
	int ceiling;
	long startTime;
	long endTime;

	printf("请输入验证哥德巴赫猜想的最大数:");
	scanf("%d", &ceiling);

	startTime = clock();
	creatPrimePool(ceiling);
	inspect(ceiling);
	endTime = clock();

	endTime -= startTime;

	printf("消耗时间:%d.%03ds", endTime / 1000, endTime % 1000);
	printf("\n");

	return 0;
}

下面是我位运算分析的链接，对位运算感兴趣的同学可以了解一下。
【C语言】->位运算详细解析->位运算的使用