筛法

筛法是重要的数论基础，介绍一下\(Eratosthenes\)和\(Euler\)筛法，还有线性筛求\(\varphi\)函数和\(\mu\)函数。

\(Eratosthenes\)筛法

也就是我们常说的埃氏筛法。
时间复杂度：\(\mathcal{O}\left(n\log\log n\right)\)
空间复杂度：\(\mathcal{O}\left(n\right)\)

原理

这是小学五年级下册的数学书，图中框出的两句话就是两种筛法思想。

我们来看黄框的思想，概括来说就是对每个数做一次素性检验。众所周知，素性检验最简单的写法是\(\mathcal{O}\left(\sqrt{n}\right)\)的，，所以总共需要\(\sum\limits_{i=1}^{n}\sqrt{i}\)（式子的展开）次计算，可见时间复杂度不优。
红框的思想就是埃筛的思想，对于每一个数标记它的倍数，我们顺序循环，如果一个数被循环到时还没被标记，那么它就是质数，这个思想很聪明，它的时间复杂度是\(\mathcal{O}\left(n\log\log n\right)\)的（OI_wiki上的证明+Mertens'Proof of Mertens'Theorem
）
我不会证，所以放一些参考资料。
在实际实现中，用\(bitset\)的效率比用\(bool\)数组高，详见OI_wiki上的数据测试，效率貌似比\(Euler\)筛要快。

\(Code\):

const int N=1e8+5;
bitset<N>bs;
ll prime[N],tot=0; 
void Eratosthenes(int n){
	bs[0]=bs[1]=true;
	for(ll i=2;i<=n;i++){
		if(!bs[i]){
			prime[++tot]=i;
			if((ll)(i*i)<=n){
				for(ll j=i*i;j<=n;j+=i){
					bs[j]=true;
				}
			}
		}
	}
}