197. 阶乘分解(素数筛)

一时失言乱红尘 2021-10-29 10:00 373阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：https://www.acwing.com/problem/content/199/  
给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci

即可。  
输入格式

一个整数N。  
输出格式

N! 分解质因数后的结果，共若干行，每行一对pi,ci  
，表示含有pcii项。按照pi

从小到大的顺序输出。  
数据范围

1≤N≤106

输入样例：

输出样例：

2 3  
3 1  
5 1

样例解释

5!=120=23∗3∗5

分析:  
把1到N个数分解在合并，复杂度过高。  
N！= N \* （N-1）*~~* 1;  
很明显，质因子不可能超过N。所以，我们可以先筛出1到N之间的每个质因子。  
现在考虑的是，N!里面有多少个质因子p。  
很明显，在1到N里面，至少包含一个质因子p的个数有N/p个。包含两个质因子p的个数有N/（p\*p）。如是而已，推出3个~~~

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int N;
    int prime[10010],top;
    int cnt[10010];
    int id[1010010];
    
    void init()
    {
        for(int i = 2; i <= N; i ++)
        {
            if(id[i] == 1)
                continue;
            prime[++ top] = i;
            for(int j = i * 2; j <= N; j += i)
            {
                id[j] = 1;
            }
        }
    
    }
    int main()
    {
        scanf("%d",&N);
        init();
    
        for(int j = 1; j <= top; j ++)
        {
            ll x = prime[j];
            while(x <= N)
            {
                cnt[j] += N / x; x = x * prime[j];
            }
            printf("%d %d\n",prime[j],cnt[j]);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/