埃拉托斯特尼筛选法

1. Intro

Eratosthenes B.C 276 ~ B.C 194
埃拉托斯特尼，古希腊数学家。完成首次日地、地月间距的测量。创立 Geography 地理学

穿越千年的优雅

2. Example :

1. 红色 $\Rightarrow$ 2 的倍数
2. 绿色 $\Rightarrow$ 3 的倍数
3. 蓝色 $\Rightarrow$ 5 的倍数
4. 橙色 $\Rightarrow$ 7 的倍数
5. 剩下 $\Rightarrow$ 质数，except 1
6. 有些数字，可以整除多个?的质数，这里以第一次筛去为准。一个合数被多次筛去，是很影响效率的冗余。

3. Why ？

所有的自然数（非负整数）中，只有 质数 和 合数 两种。

$x$是合数 $\Rightarrow$ 在自然数中，除了1和$x$（本身），还能被其他数整除
$x$是质数 $\Rightarrow$ 在自然数中，除了1和$x$（本身），不能被其他数整除

所以合数是可以被拆解的，$合数=质数\times 合数or质数$，也就是 合数 肯定是 质数 的倍数。我们可以不断筛去质数的倍数，剩下的就都是质数了?。

接下来就出现了3个问题：

1. 如何保证不会遗漏合数 ？
2. 给定的范围中，应该筛选多少个质数 ？
3. 每一个质数从哪里开始筛选，又在哪里结束呢 ？

So，第一个问题。质数$x$，倍数肯定$>x$，所以筛选的合数肯定$>x$。$x$可以放心的去筛选自己的倍数，至于$<x$的合数，是前面质数的任务。

第二个问题。看上去很好解决。so luckly，我们知道2是第一个质数；而且当某一个质数，在第一次筛选就超出了范围，it’s over，我们完成了范围内所有的筛选。

第三个问题，完全可以从$x\times x$开始筛选，因为前面的因子$2$ ~ $x-1$的结果，都已经被前面的质数筛选过了；当$x$的某一个倍数超出了范围，换下一个质数（下一个没有被筛去的数字）。

4. How ?

// struct Array {int *data; int size;};
void Era_Prime(Array *array, int max) {
	bool *temp = Era_Bool(max);
	for (int i = 2; i <= max; i++) {
		if (!temp[i]) continue;
		array->data[array->size++] = i;
	}
	free(temp);
	return ;
}

// Prime Number range 1 ~ max, include max
bool *Era_Bool(int max) {
	bool *temp = (bool *)malloc(sizeof(bool) * (max + 1));
	memset(temp, true, (max + 1));
    // 0 & 1 not matter
	temp[0] = temp[1] = false;
	for (int i = 2; i * i <= max; i++) {
		if (!temp[i]) continue;
		for (int j = i * i; j <= max; j += i) {
			temp[j] = false; // Generate double counting
		}
	}
	return temp;
}

函数返回一个 bool 数组；index $\Rightarrow$ 数字；value $\Rightarrow$ 质数 true，合数 false。

5. Hidden Crisis !

有些数字，可以整除多个不同的质数，在程序运行的过程中，就会多次重复筛选。在?的 Example 中，可以统计出：

1. 范围 $1$ ～ $50$，数字 $50$ 个
2. 质数 $15$ 个，合数 $34$ 个
3. 总筛选 $45$ 次，有效筛选 $34$ 次，重复筛选 $11$ 次
4. 有效率 $75\%$

对于今天的计算机来说，埃氏筛选法已经是很高效的算法了。即使是 $1\times 10^8$ 的范围，也可以在 $2s$ 内完成计算。但随着范围扩大，质数数量越来越稀疏，重复筛选也是会高的吓人，甚至超过有效筛选。

贪心的我们会想，还可以更快吗？

能! --Leonhard Euler