题目描述

把$N!$分解质因数

我们说两种不太一样的思路

算法1

我们把$1~n$都因式分解,把所有$p$对应的$c_i$都加起来
我们先线性筛到$\sqrt{n}$
然后只枚举质数分解每个数
这样的时间复杂度是$O(\sqrt n+\tfrac{n\sqrt n}{log\sqrt n}+n\log n)$
实际我们可以筛素数筛到n,代码好写一些

C++ 代码

#include<cstdio>
#include<string>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
int iread(){char c;int x=0,y=1;c=getchar();while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}return x*y;}
int n;
const int N=1e6+5;
bool vis[N];
int cnt[N];
int p[N],tot;
void pre(int n){
    FOR(i,2,n){
        if(!vis[i]){
            p[++tot]=i;
        }
        FOR(j,1,tot){
            int pri_j=p[j];
            if(i*pri_j>n) break;
            vis[i*pri_j]=1;
            if(i%pri_j==0){
                break;
            }
        }
    }
}
int qmax(int a,int b){
    return (a>b ? a : b);
}
int dmax=0;
void work(int x){
    int jx=x;
    FOR(i,1,tot){
        int pri=p[i];
        if(pri*pri>jx||pri>x) break;
        while(x%pri==0){
            ++cnt[pri];
            x/=pri;
            dmax=qmax(dmax,pri);
        }
    }
    if(x){
        ++cnt[x];
        dmax=qmax(dmax,x);
    }
}
int main(){
    n=iread();
    pre(n);
    FOR(i,1,n) work(i);
    FOR(j,1,tot){
        int i=p[j];
        if(i>dmax) break;
        if(cnt[i]) printf("%d %d\n",i,cnt[i]);
    }
    return 0;
}

算法2

我们从1开始,一直到n,我们找到一个数,就把它当作质数,然后开始不断乘质数,这样得到的所有数的质因数分解的结果都很好知道,然后统一加就行
时间复杂度:$O(n\log n)$

C++ 代码

int n;
const int N=1e6+5;
int cnt[N];
int cnt_[N];
int p[N],tot,top;
int vis[N];
void dfs(int x){
    FOR(j,1,tot){
        if(x*p[j]>n) return ;
        else {
            cnt_[++top]=p[j];
            if(!vis[x*p[j]]){
                FOR(l,1,top){
                    ++cnt[cnt_[l]];
                }
            }
            vis[x*p[j]]=1;
            dfs(x*p[j]);
            --top;
        }
    }
}
int main(){
    n=iread();
    FOR(i,2,n){
        if(!vis[i]){
            p[++tot]=i;
            ++cnt[i];
            cnt_[++top]=i;
            dfs(i);
            top=0;
        }
    }
    FOR(i,2,n){
        if(cnt[i]){
            printf("%d %d\n",i,cnt[i]);
        }
    }
    return 0;
}