1059. Prime Factors (25)

时间限制

50 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

HE, Qinming

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p₁^k₁* p₂^k₂ *…*p_m^k_m.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p₁^k₁ * p₂^k₂ *…*p_m^k_m, where p_i's are prime factors of N in increasing order, and the exponent k_i is the number of p_i -- hence when there is only one p_i, k_i is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<vector>
 4 using namespace std;
 5 int main()
 6 {
 7     int n,i,j;
 8     vector<int> vv;
 9     for(i=2 ;i<=10100;i++)
10     {
11         bool is = true;
12         for(j=2;j<=sqrt(i*1.0);j++)
13         {
14             if(i % j == 0)
15             {
16                 is = false;
17                 break;
18             }
19         }
20         if(is) vv.push_back(i);
21     }
22     while(scanf("%d",&n)!=EOF)
23     {
24         printf("%d=",n);
25         bool fir = true;
26         if(n == 1) printf("1");
27         else
28         {
29             i = 0;
30             while(n != 1)
31             {
32                 if(n % vv[i] == 0)
33                 {
34                     int tem = 0;
35                     while(n % vv[i] == 0)
36                     {
37                         ++tem;
38                         n = n / vv[i];
39                     }
40 
41                     if(fir)
42                     {
43                         printf("%d",vv[i]);
44                         fir = false;
45                     }
46                     else
47                     {
48                         printf("*%d",vv[i]);
49                     }
50 
51                     if(tem > 1)
52                     {
53                         printf("^%d",tem);
54                     }
55                 }
56 
57                 ++i;
58             }
59         }
60 
61         printf("
");
62     }
63     return 0;
64 }