更新日志：
- 2023/10/15：发布文章
一、埃氏筛
1. 算法原理
略
2. 时间复杂度
\(O(n\log{\log {n}})\) 详细证明见oi-wiki
3. 代码实现
bool vis[NN];
int prime[NN],cnt;
typedef long long ll;
void Era(int n){
for(ll i = 2; i <= n; ++i){
if(!vis[i]){
prime[++cnt] = i;
for(ll j = i * i; j <= n; j += i) vis[j] = 1;//尽量用long long,避免i*i溢出导致的麻烦
}
}
}
4. 相关优化
- 筛至平方根
bool vis[NN];
int prime[NN],cnt;
typedef long long ll;
void Era(int n){
for(ll i = 2; i * i <= n; ++i){
if(!vis[i]){
prime[++cnt] = i;
for(ll j = i * i; j <= n; j += i) vis[j] = 1;
}
}
for(int i = ceil(sqrt(n)); i <= n; ++i)
if(!vis[i]) prime[++cnt] = i;
}
可以将复杂度减小至\(~n\ln\ln\sqrt n + o(n)~\)
- 只筛奇数
除\(~2~\)以外的偶数都不是质数
bool vis[NN];
int prime[NN],cnt;
typedef long long ll;
void Era(int n){
prime[++cnt] = 2;//change1
for(ll i = 3; i <= n; i += 2){//change2
if(!vis[i]){
prime[++cnt] = i;
for(ll j = i * i; j <= n; j += i * 2) vis[j] = 1;//change3
}
}
}
二、 线性筛
1. 算法原理
我们考虑对埃氏筛进行优化
我们研究会发现，在埃氏筛中，一些合数会被筛多次，例如：
\(~12 = 2 \times 6 = 3 \times 4~\)，即\(~12~\)在\(\begin{cases}i = 2\\j = 6\end{cases}\)和$$\begin{cases}i = 3\j = 4\end{cases}$$会被重复筛选
那如何规避呢，我们就只让一个数最小的质因子筛这个数，让每个合数只被标记一次
2. 代码实现
bool vis[NN];
int prime[NN],cnt;
void init(){
for(int i = 2; i <= n; ++i){
if(!vis[i]) pri[++cnt] = i;
for(int j = 1; j <= cnt; ++j){
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
3. 线性筛求欧拉函数
设\(~p_1~\)为\(~n~\)的最小质因子，设\(~n'=\frac n {p_1}~\)
那么由欧拉函数定义可得：
\[\begin{cases}\varphi(n) = n\times\prod\limits_{i=1}^{s}\frac {p_i-1}{p_i} = p_1\times\varphi(n') & n'~mod~p_1 = 0\\\varphi(n) = (p_1-1)\times\varphi(n')&n'~mod~p_1\not=0\end{cases} \]再根据线性筛进行修改即可
bool vis[NN];
int prime[NN],cnt,phi[NN];
void Euler(){
phi[1] = 1;
for(int i = 2; i <= n; ++i){
if(!vis[i]){pri[++cnt] = i;phi[i] = i - 1;}
for(int j = 1; j <= cnt; ++j){
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = 1;
if(i % pri[j] == 0){
phi[i*prime[j]] = prime[j] * phi[i];
break;
}
else phi[i*prime[j]] = phi[i] * phi[prime[j]];
}
}
}