小技巧-O(W)+O(nlogn)分解质因数

好神奇啊。。。

思路 ：先用线性筛筛出值域内所有数的最大的质因数，每次查询时直接暴力除以质因数，因为每次至少减少$\frac{1}{2}$，所以单次查询复杂度是$O(lo{g}_W)$，理论上常数挺小的。

代码段($n=10^6$,$W=10^7$):

	n=read();for(int i=2;i<=10000000;++i){
    if(!vis[i]){
    p[++cnt]=i;Maxp[i]=i;}for(int j=1;p[j]*i<=10000000;++j){
    vis[p[j]*i]=1;//线性筛Maxp[p[j]*i]=max(p[j],Maxp[i]);//求最大的质因子if(i%p[j]==0)break;}}for(int i=1;i<=n;++i){
    a[i]=read();int tmp=a[i];while(tmp!=1){
    int t=Maxp[tmp];while(tmp%t==0)tmp/=t,printf("%d ",t);}puts("");}