首页 > 其他 > 详细

PAT1059Prime Factors

时间:2019-12-13 13:53:39      阅读:76      评论:0      收藏:0      [点我收藏+]
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 = 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 }

 

 

PAT1059Prime Factors

原文:https://www.cnblogs.com/gulangyuzzz/p/12034298.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!