数数论

素数筛-对阶乘分解质因数

字数统计: 914字   |   阅读时长: 4分
,

摘要: 如何对阶乘进行分解质因数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我看一个素数筛的应用问题：对阶乘分解质因数，以及后续应用，关于素数筛的算法和代码参考 素数筛。

对阶乘分解质因数

给定整数 N (1 <= n <= 1e6)，将阶乘 $N!$ 分解质因数，结果按照算术基本定理的形式输出分解结果中的 $p_{i}$ 和 $c_{i}$。

算法：素数筛

如果将 1 ~ N 均分解质因数，再把结果合并。时间复杂度为 $O(N\sqrt{N})$。

因为 $N!$ 每个质因子都不会超过 N，因此可以现将 1 ~ N 中所有素数筛出来，对筛出来的每个 p，考虑 $N!$ 中含有多少个 p。

$1 ~ N$ 中，至少含有一个 p 的有 $\lfloor \frac{N}{p}\rfloor$，至少含 2 个 p 的个数有 $\lfloor \frac{N}{p${2}}\rfloor$，在累加的时候只累加 1 个，即累加$\lfloor \frac{N}{p${2}}\rfloor$，因为 2 个 p 中的第 1 个在 $\lfloor \frac{N}{p}\rfloor$ 已经统计过了。

最终，$N!$ 中质因子 p 的个数为

对于每个 p，需要 $O(\log N)$ 求上述和。总时间复杂度为 $O(N\log N)$。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> factorial_get_prime_factor(int N, const vector<int>& primes) 
{
    int m = primes.size();
    vector<int> c(m, 0);
    for(int i = 0; i < m; ++i)
    {
        int p = primes[i];
        int cnt = 0;
        for(int j = 1; pow(p, j) <= N; ++j)
            cnt += N / pow(p, j);
        c[i] = cnt;
    }
    return c;
}

应用

用 高精度运算 求 组合数 的时候，为避免除法，可以用类似的做法对分子，分母分解质因数。然后通过质数的减法代替原数的除法。

模板题

给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

1
2
3
4
5
6
7
8
输入格式
一个整数 N。

输出格式
N! 分解质因数后的结果，共若干行，每行一对 pi,ci，表示含有 pi ^ ci 项。按照 pi 从小到大的顺序输出。

数据范围
3<=N<=1e6

输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5! = 120 = 23∗3∗5

代码 (C++)

本题是对素数分解质因数的模板题，有了 get_primes 和 factorial_get_prime_factor 这两个代码模板后，本题可以轻易解决。

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
48
49
50
51
52
53
54
55
56
57
#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

vector<int> get_primes(int n) {
    if(n < 2) return {};
    vector<bool> vec(n, true);
    vec[0] = false;
    vec[1] = false;
    int cnt = 0;
    vector<int> primes;
    for(int i = 2; i < n; ++i)
    {
        if(vec[i])
        {
            ++cnt;
            primes.push_back(i);
        }
        for(int j = 0; j < cnt && i * primes[j] < n; ++j)
        {
            vec[i * primes[j]] = false;
            if(i % primes[j] == 0)
                break;
        }
    }
    return primes;
}

vector<int> factorial_get_prime_factor(int N, const vector<int>& primes) 
{
    int m = primes.size();
    vector<int> c(m, 0);
    for(int i = 0; i < m; ++i)
    {
        int p = primes[i];
        int cnt = 0;
        for(int j = 1; pow(p, j) <= N; ++j)
            cnt += N / pow(p, j);
        c[i] = cnt;
    }
    return c;
}

int main()
{
    int N;
    cin >> N;
    vector<int> p = get_primes(N + 1);
    vector<int> c = factorial_get_prime_factor(N, p);
    int m = p.size();
    for(int i = 0; i < m; ++i)
    {
        cout << p[i] << " " << c[i] << endl;
    }
}
Share