Sieve Prime 素数筛法

一开始，我们假设所有的数都是素数，那么当我们找到一个素数时，我们把其平方后的数以及不断加上这个数本身的所有数认为是合数。

由此可以得出下面的算法

const int M = 1000; //,:size
bool mark[M];//true:prime number
void sieve_prime()
{
	memset(mark, true, sizeof(mark));
	mark[0] = mark[1] = false;
	for (int i = 2; i <= sqrt(M); i++) {
		if (mark[i]) {
			for (int j = i*i; j < M; j += i)
				mark[j] = false;
		}
	}
}

但是仔细分析就会发现，有很多数被重复的筛除了，这就导致了浪费，所以下面给出线性的素数筛法，每个数都只筛一遍，。

for (i = 2; i <= n; i++)
{
	if (mark[i])
		prime[++cnt] = i;
	for (j = 1; j <= cnt; j++)
	{
		if (i*prime[j] > n)break;
		mark[i*prime[j]] = false;
		if (i%prime[j] == 0) break;
	}
}