PAT1059Prime Factors

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
思路：算术基本定理（唯一分解定理）
用从小到大的素数整除n，vector保留素数及其对应的指数

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4
 5 using namespace std ;
 6
 7 typedef pair<int,int> PII ;
 8 vector<PII> vc ;
 9 int n ;
10
11 void get(){
12     for(int i=2;i<=n/i;i++){
13         if(n%i==0){
14             int s = 0 ;
15             while(n%i==0){
16                 s++ ;
17                 n /= i ;
18             }
19             vc.push_back({i,s}) ;
20         }
21     }
22     if(n>1){
23         vc.push_back({n,1}) ;
24     }
25 }
26
27 int main(){
28     cin >> n ;
29
30     if(n==1){
31         printf("1=1") ;
32     }else{
33         printf("%d=",n) ;
34         get() ;
35         int la = vc.size() ;
36         for(int i=0;i<la;i++){
37             if(i){
38                 printf("*") ;
39             }
40             printf("%d",vc[i].first) ;
41             if(vc[i].second>1){
42                 printf("^%d",vc[i].second) ;
43             }
44         }
45     }
46
47     return 0 ;
48 }