【堆栈应用一】一个数divided=几个最小质因数的乘积

/******************************************堆栈：一个数divided几个质因数（质因数的乘积为N）******************************************/
 1 #include<iostream>
 2 #include<stack>
 3 #include<cmath>
 4 using namespace std;
 5 bool Prime(int n);//判断质数
 6 int main()
 7 {
 8     stack<int> st;
 9     stack<int> st2;
10     int n;
11     int item=0; 
12     int product=1;
13     int temp;
14     cout<<"please input an integer"<<endl;
15     cin>>n;
16     temp=n;
17     for(int i=n;i>2;i--)
18     {
19         if(Prime(i)==true)
20             st.push(i);
21     }
22     st.push(2);    //栈顶是最小的质数
23    
24     while(product!=temp)
25     {
26        item=st.top();
27         while(n%item==0)  //直到不能再整除此质因数就跳转到下一个质因数
28         {
29             product*=item;    //记录质因数的积，直到等于n
30             n/=item;
31             st2.push(item);
32         }
33         st.pop();      //每用完一个质数都弹出，获取下一个质数
34    }
35 
36     while(! st2.empty())  
37     {  
38         cout<<st2.top()<<" ";  //逆序输出
39         st2.pop();  
40     } 
41 
42     return 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