spf(最小质因数表)分解质因数+线性筛

const int N=1e5;
vector<int> primes,spf(N+1);
void init(int n){
    for(int i=2;i<=n;i++){
        if(!spf[i]){
            spf[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(p>spf[i]||1LL*i*p>n) break;
            spf[i*p]=p;
        }
    }
}
void split(int x){
    while(x>1){
        int p=spf[x];
        int cnt=0;
        while(x%p==0){
            cnt++;
            x/=p;
        }
        cout<<p<<"^"<<cnt<<"\n";
    }
}