// 原理 每个合数都是由其最小质数所筛去
vector<int> euler_sieve(int n) { // 求n及以内的质数
vector<int> p; // 质数集合
vector<int> cp(n + 1); // cp[i] i为合数
for (int i = 2; i <= n; i++) {
if (cp[i] == 0)
p.push_back(i);
for (int j = 0; 1LL * p[j] * i <= n; j++) {
cp[p[j] * i] = 1;
if (i % p[j] == 0)
break;
}
}
for (int i : p) {
cout << i << " ";
}
cout << "\\n";
return p;
}
对于每个数$i$，我们遍历不超过$i$的最小质因子的质数$p_j$，显然$p_ji$的最小质因子就是$p_j$，我们将$p_ji$标记和合数，那么所有的合数标记的次数是$O(n)$的
vector<int> least_prime_factor(int n) { // 求n及以内的所有数的最小质因子
vector<int> p; // 质数集合
vector<int> lpf(n + 1); // lpf[i] i的最小质因子
for (int i = 2; i <= n; i++) {
if (lpf[i] == 0) {
p.push_back(i);
lpf[i] = i;
}
for (int j = 0; 1LL * p[j] * i <= n; j++) {
lpf[p[j] * i] = p[j];
if (i % p[j] == 0)
break;
}
}
lpf[1] = 1;
for (int i = 1; i <= n; i++) {
// cout << i << " " << lpf[i] << endl;
cout << lpf[i] << " ";
}
cout << "\\n";
return lpf;
}
显然$p_ji$的最小质因子就是$p_j$，所以$lpf[p_ji] = p_j$
欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目，$\phi(n) = n \times \prod \limits_{i=1}^{s}\frac{p_i-1}{p_i}$，$p_i$是$n$的质因子
vector<int> euler_phi(int n) { // 求n及以内的欧拉函数
vector<int> p; // 质数集合
vector<int> phi(n + 1);
for (int i = 2; i <= n; i++) {
if (phi[i] == 0) {
p.push_back(i);
phi[i] = i - 1;
}
for (int j = 0; 1LL * p[j] * i <= n; j++) {
phi[p[j] * i] = (p[j] - 1) * phi[i];
if (i % p[j] == 0) {
phi[p[j] * i] = p[j] * phi[i]; // i 的最小质因子是p[j]
break;
}
}
}
phi[1] = 1;
for (int i = 1; i <= n; i++) {
// cout << i << " " << phi[i] << endl;
cout << phi[i] << " ";
}
cout << "\\n";
return phi;
}
$\mu(i) = \left \{ \begin{array}{ll} 1 & i = 0 \\ 0 & i中含重复质因子\\ (-1)^k & k为i的不同质因子个数 \end{array} \right.$
vector<int> mobius(int n) { // 求n及以内的莫比乌斯函数
vector<int> p; // 质数集合
vector<int> cp(n + 1); // cp[i] i为合数
vector<int> mu(n + 1);
for (int i = 2; i <= n; i++) {
if (cp[i] == 0) {
mu[i] = -1;
p.push_back(i);
}
for (int j = 0; 1LL * p[j] * i <= n; j++) {
cp[p[j] * i] = 1;
mu[p[j] * i] = -mu[i];
if (i % p[j] == 0) {
mu[p[j] * i] = 0;
break;
}
}
}
mu[1] = 1;
for (int i = 1; i <= n; i++) {
// cout << i << " " << mu[i] << endl;
cout << mu[i] << " ";
}
cout << "\\n";
return mu;
}
$d(n) = \prod \limits_{i=1}^{s}(p_i+1)$
vector<int> cnt_divisor(int n) { // 求1到n的每个数各自的约数个数
vector<int> p; // 质数集合
vector<int> cp(n + 1); // cp[i] i为合数
vector<int> lpf_cnt(n + 1); // lpf_cnt[i] i的最小质因数的个数
vector<int> div(n + 1); // div[i] i的约数个数
for (int i = 2; i <= n; i++) {
if (cp[i] == 0) {
p.push_back(i);
lpf_cnt[i] = 1;
div[i] = 2;
}
for (int j = 0; 1LL * p[j] * i <= n; j++) {
cp[p[j] * i] = 1;
// i不含质因子p[j]，所以p[j]*i的最小质因子个数为1
lpf_cnt[p[j] * i] = 1;
// 新增一个从未出现的质数p[j]，之前的因数都可以乘以p[j]产生新的因子
div[p[j] * i] = div[i] * 2;
if (i % p[j] == 0) {
lpf_cnt[p[j] * i] = lpf_cnt[i] + 1;
// div[p[j]*i] = div[i] / (lpf_cnt[i]+1) * (lpf_cnt[i]+2)
div[p[j] * i] =
div[i] / lpf_cnt[p[j] * i] * (lpf_cnt[p[j] * i] + 1);
break;
}
}
}
div[1] = 1;
for (int i = 1; i <= n; i++) {
// cout << i << ' ' << div[i] << "\\n";
cout << div[i] << " ";
}
cout << "\\n";
return div;
}
设n的质因子分解是$\prod \limits_{i=1}^{s}p_i^{\alpha_i}$，$a(n) = \prod \limits_{i=1}^{d}\sum \limits_{j=0}^{\alpha_i}p_i^{j}$
data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7
data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7
vector<ll> sum_divisor(int n) { // 求1到n的每个数各自的约数的和
vector<int> p; // 质数集合
vector<int> cp(n + 1); // cp[i] i为合数
// i的最小质因子为p，p的个数为s，则g[i] = p^0+p^1+p^2+...+p^s
vector<ll> g(n + 1);
vector<ll> div(n + 1); // div[i] i的所有因子的和
for (int i = 2; i <= n; i++) {
if (cp[i] == 0) {
p.push_back(i);
g[i] = 1 + i;
div[i] = 1 + i;
}
for (int j = 0; 1LL * p[j] * i <= n; j++) {
cp[p[j] * i] = 1;
g[p[j] * i] = p[j] + 1;
div[p[j] * i] = div[i] * (p[j] + 1);
if (i % p[j] == 0) {
// p[j] 是i的最小质因子，若i有s个p[j]，现在有s+1个
// g[i]*p[j]+1 = (p[j]^0+p[j]^1+...+p[j]^s)p[j]+1 = g[p[j]*i]
g[p[j] * i] = g[i] * p[j] + 1;
div[p[j] * i] = div[i] / g[i] * g[p[j] * i];
break;
}
}
}
div[1] = 1;
for (int i = 1; i <= n; i++) {
// cout << i << ' ' << div[i] << "\\n";
cout << div[i] << " ";
}
cout << "\\n";
return div;
}