跳转至

筛法

欧拉筛

模版

bool: vis 数组的含义是 若 vis[x] 为 true, 则 x 不是质数, 否则 x 是质数.

int: vis 数组的含义是 vis[x] 为 x 的一个质因子, vis[x] 与 x 相等时, x 是质数 (1除外).

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace EulerSieve {
    vector<int> prime;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    break;
                }
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
namespace EulerSieve {
    vector<int> prime;
    vector<int> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = 1;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                vis[i] = i;
                prime.emplace_back(i);
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = i;
                if (i % x == 0) {
                    break;
                }
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;
例题

P3383 【模板】线性筛素数 - 洛谷

积性函数的筛法

\[ f(n*p)=\begin{cases} f(n)*f(p)&p\nmid n\\ f(n)*g(p)&p\mid n \end{cases} \]

\(f(p)\) 为一个关于 \(p\) 的简单有理函数

\(g(p)=\dfrac{f(p^{k+1})}{f(p^k)},k\ge1\) 为一个关于 \(p\) 的简单函数

欧拉函数

\(f(p)=p-1,g(p)=p\)

莫比乌斯函数

\(f(p)=-1,g(p)=0\)

约数

\(f(p)=2,g(p)=\dfrac{h(p)+2}{h(p)+1},h(p)=1,h(n)=h(p)+1\)

约数和

\(f(p)=1+p,g(p)=\dfrac{h(p)*p+1}{h(p)},h(p)=1+p,h(n)=h(p)*p+1\)

筛法求约数个数

\(d(i)\) 表示 \(i\) 的约数个数

\(num(i)\) 表示 \(i\) 的最小质因子的个数

由于 \(n=\prod_i p_i^{a_i}\)，则有 \(d(n)=\prod_i(a_i+1)\)

根据欧拉筛有三种情况

  1. \(i\) 为质数： 此时易知 \(d(i)=2，num(i)=1\)。
  2. \(i\) 不被 \(x\) 整除： 此时 \(\gcd(i,x)=1\)，即 \(d(i*x)=d(i)*d(x)，num(i*x)=1\)。
  3. \(i\) 被 \(x\) 整除： 此时可以知道 \(x\) 为 \(i*x\) 的最小质因子，可得 \(num(i*x)=num(i)+1\)。 然后因为 \(d(i)=(a_1+1)\prod_{i=2}(a_i+1)\)，\(d(i*x)=(a_1+1+1)\prod_{i=2}(a_i+1)\) 所以 \(d(i*x)=\dfrac{d(i)}{(a_1+1)}(a_1+1+1)=\dfrac{d(i)}{num(i)+1}(num(i*x)+1)=\dfrac{d(i)}{num(i*x)}(num(i*x)+1)\)
模版
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
namespace EulerSieve {
    vector<int> prime, d, num;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        d.resize(n);
        d[1] = 1;
        num.resize(n);
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                d[i] = 2;
                num[i] = 1;
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    num[i * x] = num[i] + 1;
                    d[i * x] = d[i] / num[i * x] * (num[i * x] + 1);
                    break;
                }
                num[i * x] = 1;
                d[i * x] = d[i] * 2;
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;

筛法求约数和

\(sd(i)\) 表示 \(i\) 的约数和

\(sp(i)\) 表示首项为 \(1\)，公比为 \(i\) 的最小质因子的等比数列的和

\(n=\prod_ip_i^{a_i}\)

\(sd(n)=(1+p_1+p_1^2+...+p_1^{a_1})(1+p_2+p_2^2+...+p_2^{a_2})...(1+p_k+p_k^2+...+p_k^{a_k})\)

根据欧拉筛有三种情况

  1. \(i\) 为质数： 此时易知 \(sd(i)=1+i，sp(i)=1+i\)。
  2. \(i\) 不被 \(x\) 整除： 此时 \(\gcd(i,x)=1\)，即 \(sd(i*x)=sd(i)*sd(x)，sp(i*x)=1+x\)。
  3. \(i\) 被 \(x\) 整除： 此时可以知道 \(x\) 为 \(i*x\) 的最小质因子，可得 \(sp(i*x)=sp(i)*x+1\)。 然后因为 \(sd(i)=(1+p_1+p_1^2+...+p_1^{a_1})\prod\)，\(sd(i*x)=(1+p_1+p_1^2+...+p_1^{a_1}+p_1^{a_1+1})\prod\) 所以 \(sd(i*x)=\dfrac{sd(i)}{sp(i)}sp(i*x)\)
模版
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
namespace EulerSieve {
    vector<int> prime;
    vector<long long> sd, sp;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        sd.resize(n);
        sd[1] = 1;
        sp.resize(n);
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                sd[i] = sp[i] = i + 1;
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    sp[i * x] = sp[i] * x + 1;
                    sd[i * x] = sd[i] / sp[i] * sp[i * x];
                    break;
                }
                sp[i * x] = 1 + x;
                sd[i * x] = sd[i] * sd[x];
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;