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;}}
}
