HDU1164

 1 //HDU 1164
 2 //输入一个数(1<x<=65535) 转化为素数的乘积()
 3 
 4 #include "iostream"
 5 #include "cstdio"
 6 using namespace std;
 7 
 8 int p[65535];//筛法求素数
 9 
10 void prime()
11 {
12     for(int i=2;i<65536;i++)
13     {
14         p[i]=1;
15     }
16     for(int i=2;i<65536;i++)
17     {
18         if(p[i]==1)
19         {
20             for(int j=i+i;j<65536;j+=i)
21             {
22                 p[j]=0;
23             }
24         }
25     }
26 }
27 int main()
28 {
29 
30     int a;
31     prime();
32 
33     while(~scanf("%d",&a))
34     {
35         if(p[a]==1)//若为素数直接输出
36         {
37             printf("%d
",a);
38         }
39         else//不为素数从小到大分解输出
40         {
41             for(int i=2;i<=a;i++)
42             {
43                 if(p[i]==1)
44                 {
45                     if(a%i==0)
46                     {
47                         a/=i;
48                         if(a==1)
49                         {
50                             printf("%d
",i);
51                             break;
52                         }else
53                         {
54                             printf("%d*",i);
55                             i=1;
56                         }
57                     }
58                 }
59             }
60         }
61     }
62 }
View Code