\(i\) 的最小质因数 \(pm[i]\) 。
\(i\) 的最大的最小质因数的幂 \(pk[i]\) 。
判断 \(i\) 是不是质数的充要条件为 \(i>1 \; and \; pm[i]=i\)
const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN];
void sieve(int n) {
memset(pm, 0, sizeof(pm[0]) * (n + 1));
ptop = 0, pm[1] = 1, pk[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!pm[i])
p[++ptop] = i, pm[i] = i, pk[i] = i;
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
pm[t] = p[j];
if(i % p[j])
pk[t] = pk[p[j]];
else {
pk[t] = pk[i] * p[j];
break;
}
}
}
}
数论函数
除数函数 \(\sigma_k(n)\) : \(n\) 的因子的 \(k\) 次方和,当 \(k=0\) 时,为 \(n\) 的因数个数 \(d(n)\) 。
\(i\) 的因数个数 \(pd[i]\)。
\(i\) 的最大的最小质因数的幂 \(pk[i]\) 。
const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], pd[MAXN];
void sieve(int n) {
memset(pm, 0, sizeof(pm[0]) * (n + 1));
ptop = 0, pm[1] = 1, pk[1] = 1, pd[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!pm[i]) {
p[++ptop] = i, pm[i] = i;
pk[i] = i, pd[i] = 2;
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
pm[t] = p[j];
if(i % p[j]) {
pk[t] = pk[p[j]];
pd[t] = pd[i] * pd[p[j]];
} else {
pk[t] = pk[i] * p[j];
pd[t] = (pk[t] == t) ? pd[t / p[j]] + 1 : pd[t / pk[t]] * pd[pk[t]];
break;
}
}
}
}
Euler函数:
const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], phi[MAXN];
void sieve(int n) {
memset(pm, 0, sizeof(pm[0]) * (n + 1));
ptop = 0, pm[1] = 1, pk[1] = 1, phi[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!pm[i]) {
p[++ptop] = i, pm[i] = i;
pk[i] = i, phi[i] = i - 1;
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
pm[t] = p[j];
if(i % p[j]) {
pk[t] = pk[p[j]];
phi[t] = phi[i] * phi[p[j]];
} else {
pk[t] = pk[i] * p[j];
phi[t] = (pk[t] == t) ? t - t / p[j] : phi[t / pk[t]] * phi[pk[t]];
break;
}
}
}
}
Mobius函数
const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], mu[MAXN];
void sieve(int n) {
memset(pm, 0, sizeof(pm[0]) * (n + 1));
ptop = 0, pm[1] = 1, pk[1] = 1, mu[1] = 1;
for(int i = 2; i <= n; ++i) {
if(!pm[i]) {
p[++ptop] = i, pm[i] = i;
pk[i] = i, mu[i] = -1;
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
pm[t] = p[j];
if(i % p[j]) {
pk[t] = pk[p[j]];
mu[t] = mu[i] * mu[p[j]];
} else {
pk[t] = pk[i] * p[j];
mu[t] = (pk[t] == t) ? 0 : mu[t / pk[t]] * mu[pk[t]];
break;
}
}
}
}
任意的积性函数
分为1,质数,质数的幂三种不同情形,其他的用积性函数的性质得到。
const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], f[MAXN];
void sieve(int n) {
memset(pm, 0, sizeof(pm[0]) * (n + 1));
ptop = 0, pm[1] = 1, pk[1] = 1, f[1] = getF1();
for(int i = 2; i <= n; ++i) {
if(!pm[i]) {
p[++ptop] = i, pm[i] = i;
pk[i] = i, f[i] = getFp(i);
}
for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
pm[t] = p[j];
if(i % p[j]) {
pk[t] = pk[p[j]];
f[t] = f[i] * f[p[j]];
} else {
pk[t] = pk[i] * p[j];
f[t] = (pk[t] == t) ? getFpk(t, p[j]) : f[t / pk[t]] * f[pk[t]];
break;
}
}
}
}