/******************************************堆栈：一个数divided几个质因数（质因数的乘积为N）******************************************/
1 #include<iostream> 2 #include<stack> 3 #include<cmath> 4 using namespace std; 5 bool Prime(int n);//判断质数 6 int main() 7 { 8stack<int> st; 9stack<int> st2;10int n;11int item=0; 12int product=1;13int temp;14cout<<"please input an integer"<<endl;15cin>>n;16temp=n;17for(int i=n;i>2;i--)18{19 if(Prime(i)==true)20 st.push(i);21}22st.push(2); //栈顶是最小的质数23 24while(product!=temp)25{26 item=st.top();27 while(n%item==0) //直到不能再整除此质因数就跳转到下一个质因数28 {29 product*=item; //记录质因数的积，直到等于n30 n/=item;31 st2.push(item);32 }33 st.pop();//每用完一个质数都弹出，获取下一个质数34 }35 36while(! st2.empty()) 37{ 38 cout<<st2.top()<<" "; //逆序输出39 st2.pop(); 40} 41 42return 0;43 } 44 bool Prime(int n)45 {//判断n是否是质数46 bool isPrime=true;47 for(int i=sqrt(n);i>1;i--)48 {49 isPrime=true;50 if(n%i==0)51 {//如果有能被整除的，则不是质数52 isPrime=false;53 }54 } 55 return isPrime; 56 }57
输入2100，输出7 5 5 3 2 2
时间复杂度n+logn
