「学习笔记」埃拉托斯特尼筛法和线性筛法

埃拉托斯特尼筛法

简称埃氏筛。对于一个大于 11 的正整数，它的 xx 倍就是一个合数。当我们从小到大编历时，就可以将当前遍历的数的倍数都打上标记不可访问，到运行结束后没有被标记的就是质数了。

考虑优化，只需要枚举到 \(\sqrt{n}\) 即可。这样时间复杂度是 \(O(n log log n)\)。

vector <int> prime;
bool is_prime[maxn];

void iss (int n) {
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) is_prime[i] = true;
	for (int i = 2; i * i <= n; i++) {
		if (is_prime[i])
			for (int j = i * i; j <= n; j += i) is_prime[j] = false;
	}
	for (int i = 2; i <= n; i++) 
		if (is_prime[i]) prime.push_back(i);
}

线性筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。让每一次合数都指标记一次就会加快速度，从而将时间复杂度降到 O(n)O(n)。

int prime[maxn];
bool isPrime[maxn];

void xxs (ll n) {
	int cnt = 0;
	memset (isPrime, 1, sizeof(isPrime));
	isPrime[1] = 0;
	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) 
			prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
			isPrime[i * prime[j]] = 0;
			if (i % prime[j] == 0)
				break;
		}
	}
}

这段代码中，if (i % prime[j] == 0) break;这行代码来控制每个合数只由它的最小质因数筛掉。

举一个直观地例子：i=30=2×3×5，此时我们的 prime[j] 只能是 2 不能是往下的 3，也就是只筛它的最小值因子。接着往下，当 j=45=3×3×5 时，如果在筛 i 的时候筛了 3，就会重复筛 45，也就是说 45 被筛了两次。根据线性筛的原理，只需要筛一次即可。

虽然埃氏筛比较好写且好记，但是遇到 \(10^9\) 往上的毒瘤卡埃筛的数据时还是无能为力，所以写线性筛就行了。