[Algorithm]Sieve of Eratosthenes

要寻找所有< N的素数，我们应该怎么做？Naive的做法是对于所有< N的数字i我们判断i是否是素数，这样时间复杂度为O(N ^ (3/2))。有没有更快的做法呢？
Sieve of Eratosthenes可以让我们在O(N)的时间解决这个问题，同时我们要付出O(N)的空间作为代价。具体的思路为，我们用一个array来表示array[i]是否为素数，默认所有entry设为true，对于所有2 <= i <= N的整数i：

1. 如果array[i]为false， continue
2. 如果i >=sqrt(N)我们将i加入结果集
3. 如果i < sqrt(N)并且array[i]为true，将i加入结果集，并且将所有array[k * i](i <= k, k * i < n)标记为false，表示这个数不是素数，因为他有不等于1和它本身的因子i

这个算法为什么是正确的？对于整数i我们有结论当：我们遍历到i并且array[i]为true，那么i一定是素数，因为：

• 如果i == 2，array[2]默认为true
• 如果array[i]为true，那么代表i没有因子x, where 1<x<i，因为如果x存在，在前面的某次循环i一定会被标为false

代码如下：

	int countPrimes(int n) {
	int count = 0;
	vector<bool> isPrime(n, true);
	for (int i = 2; i < n; ++i)
	{
	if(isPrime[i])
	{
	++count;
	if(i >= sqrt(n))continue；
	for (int j = i * i; j < n; j += i)isPrime[j] = false;
	}
	}
	return count；
	}

view raw sieve_of_eratosthenes.cxx hosted with ❤ by GitHub

几个值得注意的细节：

• 为什么j从i*i开始？因为i*k(k < i)已经被标为false了，例如i = 3，我们不用从6开始，因为6在i = 2的循环已经被标为false了
• 为什么i >=sqrt(N)之后我们就直接加入结果集而不做后续的处理？因为i*i>N超出了我们要考虑的范畴