质因数分解

单个数的分解

预处理出1~sqrt(n)的质数，每次读入一个数，判断能否被这些质数整除即可（有很多数，且都较大）
循环1~sqrt(n),判断能否被整除（只有几个数）

n!的分解

结合线性筛法，复杂度为O(n)

#define MAXN 1000005
int tag[MAXN],ans[MAXN],n,Prim[MAXN],num;

void find(int n){
    int j;
    for(int i=2;i<=n;i++){
        if(!tag[i]) Prim[++num]=i;
        for(j=1;j<=num;j++){
            if(i*Prim[j]>n)
                break;
            tag[i*Prim[j]]=i;
            if(i%Prim[j] == 0)
                break;
        }
    }
    for (int i=2;i<=n;++i) ans[i]=1;
    for (int i=n;i>=2;--i){
        if (tag[i]){
            ans[i/tag[i]]+=ans[i];
            ans[tag[i]]+=ans[i];
            ans[i]=0;
        }
    }
    for (int i=2;i<=n;++i){
        if (ans[i]) printf("%d %d\n",i,ans[i]);
    }
}

约数分解

1~n所有正约数的分解

用倍数法，复杂度为O(n log n)

vector<int> ans[MAXN];
int n;

void find(int n){
    for (int i=2;i<=n;++i){
        for (int j=i;j<=n;j+=i){
            ans[j].push_back(i);
        }
    }
    for (int i=2;i<=n;++i){
        for (int j=0;j<ans[i].size();++j) printf("%d ",ans[i][j]);
        puts("");
    }
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/89/