埃拉托斯特尼筛法（埃氏筛）

小学的时候，老师就讲过，质数是因数只有 $1$ 和它自己的数字，于是我们很容易推出，如果一个数是质数，那么它的倍数一定是合数。

于是

• 我们从 $2$ 开始，如果当前的数字 $i$ 没有被标记为合数，那么他就是质数。
• 然后把 $i$ 的所有倍数都标记为合数。
• 继续下一个数。

我们就可以得到这样一个程序：

vector<int> primes;
vector<bool> vis(maxn + 1);

void init() {
	primes.push_back(1);	//把1放进去用于构造1-base索引，部分情况下也需要用到“第0个质数是1”
	for (int i = 2; i <= maxn; ++i) {
		if (!vis[i]) {
			primes.push_back(i);
			for (int j = i + i; j <= maxn; j += i) {
				vis[j] = 1;
			}
		}
	}
}

时间复杂度为 $O(nloglogn)$ 。

欧拉筛（线性筛）

虽然埃氏筛的时间复杂度只比线性多了一些，但是仍有被卡常的风险，于是我们使用线性时间复杂度的欧拉筛。

根据上面的描述我们知道，埃氏筛中一个数字会被它的所有质因数标记，要想优化掉重复标记的时间，我们需要保证每个合数都只被它最小的那个质因数标记。

于是：

• 对于每个 $i$ ，如果 $i$ 没有被标记，那么它就是质数。
• 遍历所有已经生成的质数
  • 标记 $p*i$ 为合数
  • 如果 $i$ 能被 $p$ 整除，就break 。

vector<int> primes, spf(maxn + 1);

void init() {
	primes.push_back(1);	//把1放进去用于构造1-base索引，部分情况下也需要用到“第0个质数是1”
	for (int i = 2; i <= maxn; ++i) {
		if (!vis[i]) primes.push_back(i);
		for (int j = 1; primes[j]*i <= maxn; ++j) {
			int m = primes[j] * i;
			spf[i] = primes[j];
			if (i % primes[j] == 0) break;
		}
	}
}

那为什么 break 能保证线性。我们分两种情况讨论：

• $p < spf[i]$
  • 那么 $p$ 比 $i$ 的最小质因子要小。
  • 说明 $p$ 是 $i*p$ 的最小质因子，我们要标记它。
• $p == spf[i]$
  • 那么 $i*p$ 的最小质因子还是 $p$ 。
  • 我们标记完 $i*p$ 后，需要停止找更大的质数，如果我们使用了更大的质数 $q$ ，因为 $spf[i]==p$ ，所以 $i*q$ 的最小质因子还是 $p$ ，就会发生重复标记。

所以我们需要 $i%p==0$ 就 $break$ 。

时间复杂度为 O(n) 。