[数据结构与算法]2022.1.28 训练日记 6 AcWing 197. 阶乘分解

题目链接：阶乘分解

题目分析：

0.筛素数的题。
1.暴力做法：
	1.1 把阶乘乘出来再做质因数分解不可行。
	1.2 依次对每个数 质因数分解。时间复杂度为O(n * 根号n)
2.步骤如下：
	2.1 筛出1~1e6 中的 质数。
	2.2 求p的次数：n/p + n/p^2 +  n/p^3 ........  时间复杂度为O(log p n);

code:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init (int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int main()
{
    
    int n;
    cin >> n;
    init(n);
    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int s = 0;//当前质数的次数
        for(int j = n; j ; j /= p) s += j / p;//求p的次方
        printf("%d %d\n", p, s);
    }
    return 0;
}

总结：

1.一百万里面大概有80000个质数。
2.做数论的题多分析时间复杂度。