阶乘分解

2020-08-04 本文已影响0人 dachengquan

题目链接：阶乘分解
分解阶乘的质因数。
将1~N每个数，分别分解质因数合并的时间复杂度是 $O(N\sqrt N)$ 。
对于N！来说假设p<N，并且p是质数。那么N！以p为质因数的数有， $p，2*p,...,\lfloor \frac N p \rfloor*p$ 一共是 $\lfloor \frac N p \rfloor$ 个，每个都至少包含了一个质因子p。至少包含两个质因数的是 $\lfloor \frac N {p^2} \rfloor$ 。 $\lfloor \frac N {p^2} \rfloor$ 最少包含两个质因子p，不过其中一个质因子已经被 $\lfloor \frac N p \rfloor$ 统计过一次。
N！中质因子p的个数是 $\lfloor \frac N p \rfloor+\lfloor \frac N {p^2} \rfloor+\lfloor \frac N {p^3} \rfloor+...$
时间复杂度大概是 $O(n\log n)$ 。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1000010;
vector<int> p;
bool v[N];
void get_prime(int n){
    for(int i = 2;i<=n;i++){
        if(v[i]==0)p.push_back(i);
        for(int j = 0;i*p[j]<=n;j++){
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
int main(){
    
    int n;
    cin>>n;
    get_prime(n);
    for(int i = 0;p[i]<=n&&i<p.size();i++){
        int ans = 0;
        for(int k = n;k;k/=p[i]){
            ans+=k/p[i];
        }
        cout<<p[i]<<" "<<ans<<endl;
    }
}

阶乘分解

猜你喜欢

热点阅读