题目样例给的不是很严谨，求改正。@AC君

删去49-51行不影响AC。出题者给的样例中，分解后的所有因数没有一个大于根号n小于n本身的。如果有这种样例，该代码是无法正常运行的（如删去后输入10000000007会输出23 * 2293，但正确分解为23 * 2293 * 189613）**以下为正确代码：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool mark[1000002],fag;
vector<int>prime;
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    ll n;
    cin>>n;
    
    int k=sqrt(n);
    k++;
    for(int i=2;i<=k;i++){
        if(!mark[i]){           
            prime.push_back(i);
            for(int j=2*i;j<=k-i;j+=i){
                mark[j]=1;
            }
        }
    }
    int k2=prime.size();
    
    for(int i=0;i<k2;i++){
        cnt=0;
        //cout<<prime[i]<<endl;
        while(n%prime[i]==0){
            cnt++;
            n/=prime[i];
        }
        if(cnt==0)continue;
        else if(cnt==1){
            //cout<<prime[i]<<endl;
            if(!fag){cout<<prime[i];fag=1;}
            else{
                cout<<" * "<<prime[i];
            }
        }else{
            if(!fag){cout<<prime[i]<<'^'<<cnt;fag=1;}
            else{
                cout<<" * "<<prime[i]<<'^'<<cnt;
            }
        }
    }
    if(!fag){
        cout<<n;
    }
    else if(n!=1){
        cout<<" * "<<n;      
    }
    return 0;
}