/******************************************堆栈：一个数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
转载于:https://www.cnblogs.com/tenderwx/p/5279732.html
