总时间限制: 1000ms 内存限制: 65536kB描述
输入一个数,输出其素因子分解表达式。
输入输入一个整数 n (2 <= n < 100)。输出输出该整数的因子分解表达式。 表达式中各个素数从小到大排列。 如果该整数可以分解出因子a的b次方,当b大于1时,写做 a^b ;当b等于1时,则直接写成a。样例输入
60
样例输出
2^2*3*5
来源习题(9-3)
1 #include<iostream>
2 #include<cmath>
3 using namespace std;
4 int vis[10001];
5 int zs2;
6 int zs3;
7 int zs5;
8 void f(int &n)
9 {
10 if(n%2==0)
11 {
12 zs2++;
13 n=n/2;
14 f(n);
15 }
16 else if(n%3==0)
17 {
18 zs3++;
19 n=n/3;
20 f(n);
21 }
22 else if(n%5==0)
23 {
24 zs5++;
25 n=n/5;
26 f(n);
27 }
28 }
29 int main()
30 {
31
32 int n;
33 cin>>n;
34 for(int i=2;i<=sqrt(n+0.5);i++)
35 {
36 if(vis[i]==0)
37 {
38 for(int j=i*i;j<=n;j=j+i)
39 vis[j]=1;
40 }
41 }//筛法求素数
42 f(n);
43 int flag=0;
44 if(zs2==1)
45 {
46 cout<<"2";
47 flag=1;
48 }
49 else if(zs2>0)
50 {
51 cout<<"2^"<<zs2;
52 flag=1;
53 }
54
55 if(zs3==1)
56 {
57 if(flag==1)
58 {
59 cout<<"*3";
60 flag=2;
61 }
62 else
63 {
64 cout<<"3";
65 flag=2;
66 }
67 }
68 else if(zs3>1)
69 {
70 if(flag==1)
71 {
72 cout<<"*3^"<<zs3;
73 flag=2;
74 }
75 else
76 {
77 cout<<"3^"<<zs3;
78 flag=2;
79 }
80 }
81 //cout<<"3^"<<zs3<<"*";
82 if(zs5==1)
83 if(flag==1||flag==2)
84 {
85 cout<<"*5";
86 flag=3;
87 }
88 else
89 {
90 cout<<"5";
91 flag=3;
92 }
93 else if(zs5>0)
94 if(flag==1||flag==2)
95 {
96 cout<<"*5^"<<zs5;
97 flag=3;
98 }
99 else
100 {
101 cout<<"5^"<<zs5;
102 flag=3;
103 }
104 if(n!=1)
105 cout<<"*"<<n<<endl;
106
107 return 0;
108 }