利用Eratosthenes筛选法计算质数

       算法第1步就是写下从3至某个上限之间的所有奇数。在算法的剩余部分，遍历整个列表并剔除所有不是质数的奇数。在3之后把每逢第3个数（3的倍数）剔除。完成这一步之后，轮到5，将所有5的倍数剔除。这样依次类推、反复进行，最后列表中未被剔除的数均为质数。

      这里可能读者会有问题了，为什么轮到4、6、8、10等等之类的数字呢？原因在于，我们待筛选的列表中的所有数字都是奇数。一开始就直接从奇数空间寻找质数（偶数除2之外都不是质数），那么用4、6、8、10之类的数字作为标准参与剔除过程是不必要的，奇数和这类数字肯定没有公约数。自然筛选完成之后是没有发生改变的。

      这样可能还是比较抽象，我将用一张示意图进行说明：

红色标记代表已经被剔除

        每个数组元素的值用于标记对应的数是否已被剔除。开始时所有元素的值都设置为TRUE（值为1），当算法要求“剔除”其对应的数字时，就把这个元素设置为FALSE（值为0）。

       以上处理都完成了之后，准备输出列表中的数字，注意，列表只是一个逻辑概念，并不真实存在，所以用本算法会使得程序的空间效率大大提高。并不是列表中的任意数字都能输出的，只有该数字对应的数组元素的值为TRUE是才能够输出。

      我们回顾一下传统的找寻质数的办法，最大的缺陷就是把所有待筛选的数字都放在数组里面，并没有充分利用下标，大大浪费了空间。

#define SIZE 20
#define TRUE 1
#define FALSE 0
#include<stdio.h>
 
int main() {
	char sieve[SIZE];
	char *sp;
	int number;
	for (sp = sieve; sp < &sieve[SIZE];)
		*sp++ = TRUE;
	for (number = 3;; number += 2) {
		sp = &sieve[0] + (number - 3) / 2;
		if (sp >= &sieve[SIZE])
			break;
		while (sp += number, sp < &sieve[SIZE])
			*sp = FALSE;
	}
	printf("2\n");
	for (number = 3, sp = &sieve[0];
		sp < &sieve[SIZE];
		number += 2, sp++) {
		if (*sp)
			printf("%d\n", number);
	}
	return 0;
}

本程序在VS2017下运行通过，环境不同可能会造成困扰。