质数筛法

1. 埃拉托斯特尼筛法

从小到大枚举每一个数 \(x\)，考虑标记每一个合数，如果 \(x\) 没被标记，那么它就是质数，所以 \(x \times i\) 就是合数，将它们标记，由于小于 \(x^2\) 的 \(x\) 的倍数之前已经筛过了，所以从 \(x^2\) 开始。最后没被标记的就是质数，复杂度 \(\mathcal{O}(n \log n \log n)\)。

这种筛法可以进行优化，例如枚举到 \(\sqrt{n}\)，只筛奇数，bitset 优化等等，甚至可以快过线性筛法。

bitset<N> not_prime;
not_prime[1]=1;
for(int i=2;i*i<=n;i++)
{
   if(not_prime[i]==0)
	{
		for(int j=i*i;j<=n;j+=i)
		{
			not_prime[j]=1;
		}
	}
}
For(i,1,n)
{
	if(!not_prime[i]) prime[++cnt]=i;
}

2. 欧拉筛

埃氏筛法会将一个合数重复多次标记。如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 \(\mathcal{O}(n)\) 了。

考虑让每一个合数只被其最小质因子标记。还是从小到大枚举每一个数 \(i\)，标记每一个合数，维护一个质数的序列 \(p\)，如果 \(i\) 没被标记，那么将它加入这个序列，接下来遍历这个序列（无论 \(i\) 是不是一个质数），标记 \(i \times p_j\) 为合数，如果 \(i\) 是 \(p_j\) 的倍数，那么就可以直接 \(\texttt{break}\) 了，这是由于：

如果不 \(\texttt{break}\) 的话，那么 \(i \times p_{j+1}\) 就会被 \(p_{j+1}\) 标记，而 \(p_j \mid i\)，所以 \(p_j\) 也是 \(i \times p_{j+1}\) 的一个质因数，由于序列 \(p\) 是递增的，所以 \(p_j < p_{j+1}\)，所以 \(p_{j+1}\) 不是 \(i \times p_{j+1}\) 的最小质因子，违背了每一个合数只被其最小质因子标记的原则，所以需要 \(\texttt{break}\)。

for(int i=1;i<=n;i++)
{
	if(!notprime[i])
	{
		prime[++cnt]=i;
	}
	for(int j=1;j<=cnt&&(long long)i*prime[j]<n;j++)
	{
		notprime[i*prime[j]]=1;
		if(i%prime[j]==0)
		{
			break;
		}
	}
}