跳转至

素数

素数定理

\(\pi(x)\) 为 \([1,x]\) 中的素数个数

随着 \(x\) 的增长 \(\dfrac{\pi(x)}{\frac{x}{\ln(x)}}=1\)

基本定理

\(n=p_1^{\alpha_1}*p_2^{\alpha_2}*...*p_k^{\alpha_k}\)

约数个数 \(d(n)=(\alpha_1+1)*(\alpha_2+1)*...*(\alpha_k+1)\)

约数之和 \(\phi(n)=\dfrac{p_1^{\alpha_1+1}-1}{p_1-1}*\dfrac{p_k^{\alpha_k+1}-1}{p_k-1}*...*\dfrac{p_k^{\alpha_k+1}-1}{p_k-1}\)

\(n!\) 因子 \(p\) 的数量为 \(\lfloor\dfrac{n}{p^1}\rfloor+\lfloor\dfrac{n}{p^2}\rfloor+...+\lfloor\dfrac{n}{p^{+\infty}}\rfloor\)

素数判断

模版

根号枚举所有小因子

代码
C++
1
2
3
4
5
6
7
bool is_prime(i64 x) {
    if (x < 2) return false;
    for (int i = 2 ; 1LL * i * i <= x ; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
namespace Miller_Rabin {
    using i64 = long long;
    i64 qpow(__int128 a, i64 b, i64 P) {
        __int128 res = 1;
        while (b) {
            if (b & 1) res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }
    bool Miller_Rabin(i64 n, const vector<i64> &as) {
        i64 d = n - 1;
        while (d % 2 == 0) {
            d /= 2;
        }
        i64 e = 1, rev = n - 1;
        for (auto &a : as) {
            if (n <= a) {
                break;
            }
            i64 t = d;
            __int128 y = qpow(a, t, n);
            while (t != n - 1 && y != e && y != rev) {
                y = y * y % n;
                t *= 2;
            }
            if (y != rev && t % 2 == 0) {
                return false;
            }
        }
        return true;
    }
    bool is_prime(i64 n) {
        if (n % 2 == 0) {
            return n == 2;
        }
        if (n <= 1) {
            return false;
        }
        if (n < (1LL << 30)) {
            return Miller_Rabin(n, {2, 7, 61});
        }
        return Miller_Rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    }
} // Miller_Rabin
using Miller_Rabin::is_prime; // 判断是否是质数

梅森素数

如果 \(m\) 是一个正整数，且 \(2^m-1\) 是一个素数，则 \(m\) 是素数。反之，如果 \(m\) 是一个正整数，素数且 \(M_m=2^m-1\)称作为第 \(m\) 个梅森数；如果 \(p\) 是一个素数，并且 \(M_p=2^p-1\) 也是一个素数，则 \(M_p\) 成为梅森素数。

洛谷U313346

U313346 【模板】Lucas-Lehmer - 洛谷

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
long long datas[64];
bool Lucas_Lehmer(int p) {
    if (p == 2) {
        return true;
    }
    datas[1] = 4;
    long long mod = (1LL << p) - 1;
    for (int i = 2 ; i <= p - 1 ; i++) {
        datas[i] = (((__int128)datas[i - 1] * datas[i - 1] % mod) - 2) % mod;
    }
    return datas[p - 1] == 0;
}