我们都知道算术基本定理，贴一波百度百科。

定理描述得很简单，也很好理解。但实际上，要想得到一个数的素因数分解式并不简单。

最简单的办法是暴搜，稍微好一点的方法是利用欧拉筛。

1 int n,vis[maxn],prime[maxn],cnt,minf[maxn]; 2 int main() { //minf[i]保存i的最小素因数  3     scanf("%d",&n); 4     for(int i=2;i<=n;++i) { //进行欧拉筛的同时记录minf[i]  5         if(!vis[i]) {prime[++cnt]=i;minf[i]=i;} 6         for(int j=1;j<=cnt&&i*prime[j]<=n;++j) { 7             vis[i*prime[j]]=1; 8             minf[i*prime[j]]=prime[j]; 9             if(i%prime[j]==0) break;10         }11     } 12     for(int i=2;i<=n;++i) { 13         int j=i; //不断进行分解 14         while(j>1) {printf("%d ",minf[j]);j/=minf[j];}15         printf("\n");16     }17     return 0;18 }