蓝桥杯算法提高VIP-质因数2-题解(C++代码)

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int p[100];
    int k=0;
    for(int i=2;i<=n;i++){
        if(n%i==0){
            n=n/i;
            p[k++]=i;
            i=1;
            if(n==1){
                break;
            }
        }
    }
    //折半插入
    int i,j,temp,m,low,high;
    for(int i=1;i<k;i++){
        low=0;
        high=i-1;
        while(low<=high){
            m=(low+high)/2;
            if(p[m]>p[i]){
                high=m-1;
            }else{
                low=m+1;
            }
        }
        temp=p[i];
        for(j=i;j>high+1;j--){
            p[j]=p[j-1];
        }
        p[high+1]=temp;
    }
    //输出
    for(int i=0;i<k;i++){
        cout<<p[i]<<" ";
    }
    cout<<endl;
    cout<<k<<endl;
    return 0;
}