注意：线性筛基本可以求出所有积性函数，外层循环都是从2开始的
一、线性筛求质数与欧拉函数
二、线性筛求约数个数
\(设n=\prod_{i=1}^{q}p_i^{r_i}，则约数个数函数fac(n)=\prod_{i=1}^{q}r_i+1，为积性函数（指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数）。辅助数组minp(i)表示i最小质因数的次幂。\)
\[\left\{
\begin{array}{lr}
i为质数，fac(i)=2,midp(i)=1& \ i与p互质，fac(i?p)=fac(i)?fac(p)=fac(i)?2,minp(i?p)=1& \ i与p不互质p是i最小素因子，fac(i?p)=\frac{fac(i)}{minp(i)+1} ?(minp(i)+2),minp(i?p)=minp(i)+1& \ \end{array}
\right.\]
void Fac(int n) {
fac[1] = 1, minp[1] = 0;
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
p[++w] = i; fac[i] = 2; minp[i] = 1;
}
for (int j = 1; j <= w && i*p[j] <= n;j++) {
flag[i * p[j]] = 1;
if (i % p[j] == 0) {
fac[i * p[j]] = fac[i] / (minp[i] + 1) * (minp[i] + 2);
minp[i * p[j]] = minp[i] + 1;
break;
} else {
fac[i * p[j]] = fac[i] * 2;
minp[i * p[j]] = 1;
}
}
}
}
三、线性筛求约数和
\(设n=\prod_{i=1}^{q}p_i^{r_i}，则约数和函数sumd(n)=\prod_{i=1}^{q}\sum_{k=0}^{r_i}p_i^k，为积性函数（指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数）。辅助数组minp(i)表示i最小质因数的次幂。\)
\[\left\{
\begin{array}{lr}
i为质数，sumd(i)=i+1,midp(i)=i& \ i与p互质，sumd(i?p)=sumd(i)?sumd(p)，midp(i)=midp(p)=p& \ i与p不互质p是i最小素因子，sumd(i?p)=\frac{sumd(i)}{minp(i)-1} ?(minp(i)^2-1)，minp(i?p)=minp(i)*p& \ \end{array}
\right.\]
void Sumd(int n) {
sumd[1] = 1, minp[1] = 0;
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
p[++w] = minp[i] = i; sumd[i] = i + 1
}
for (int j = 1; j <= w && i * p[j] <= n; j++) {
flag[i * p[j]] = 1;
if(i % p[j] == 0) {
sumd[i * p[j]] = sumd[i] * (minp[i] * p[j] * p[j] - 1) / (minp[i] * p[j] - 1);
minp[i * p[j]] = minp[i] * p[j];
break;
} else {
sumd[i * p[j]] = sumd[i] * sumd[p[j]];
minp[i * p[j]] = p[j];
}
}
}
}
四、线性筛求莫比乌斯函数
默比乌斯函数，也称为莫比乌斯函数、缪比乌斯函数在数论中有着广泛应用。
性质：
\(①\)
\[ \sum_{d|n}\mu(d)=\left\{
\begin{aligned}
1 & ， & n=1 \0 & ， & n=0
\end{aligned}
\right.
\]
\(②对任意正整数n有：\)
\[\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}
\]
\[ \mu(n)=\left\{
\begin{aligned}
1 & ， && n=1 \(-1)^k & ， && n=\prod_{i=1}^{k}p_i \0 & ， && n有大于1的平方数因数
\end{aligned}
\right.
\]
void Mu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
mu[i] = -1; p[++w] = i;
}
for (int j = 1; j <= w && i * p[j] <= n; j++) {
flag[i * p[j]] = 1;
if (!(i % p[j])) {
mu[i * p[j]] = 0;
break;
} else mu[i * p[j]] = -mu[i];
}
}
}
证明自己去查吧（逃