1059 Prime Factors (25分)

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p​1​​​k​1​​​​×p​2​​​k​2​​​​×⋯×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​1​​^k​1​​*p​2​​^k​2​​*…*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 #define _CRT_SECURE_NO_WARNINGS
 2 #include <climits>
 3 #include<iostream>
 4 #include<vector>
 5 #include<queue>
 6 #include<map>
 7 #include<set>
 8 #include<stack>
 9 #include<algorithm>
10 #include<string>
11 #include<cmath>
12 using namespace std;
13 vector<int> V(50000, 1);
14 int main()
15 {
16     for (int i = 2; i * i <50000; i++)
17         for (int j = 2; j * i <50000; j++)
18             V[i * j] = 0;
19     long long N;
20     cin >> N;
21     cout << N << "=";
22     if (N == 1)
23         cout << "1";
24     bool statu = false;
25     for (int i = 2; i< N&&N>=2; i++)
26     {
27         int count = 0, flag = 0;
28         while (V[i]&&N%i==0)
29         {
30             flag = 1;
31             count++;
32             N /= i;
33         }
34         if (flag)
35         {
36             if (statu)cout << "*";
37             cout << i;
38             if (count > 1)
39                 cout << "^" << count;
40             statu = true;
41         }
42     }
43     if (N > 1)
44         if (statu)cout << "*" << N;
45         else cout << N;
46 }

View Code