高中生程式解題:c088: 00516 - Prime Land－資工趴趴熊的小天地

Content

在質數國中人們使用以質數為基底的數字系統來表達一個整數。若以我們的觀點來看的話，就是每一個大於1的整數X都用唯一的因數分解的形式來表現。即

X = Pkex * ...... * P1e1 * P0e0

例如：我們的整數40在質數國中以：5 1 2 3來表示。（表示5的1次方乘以2的3次方）

這樣的系統對我們來說實在是不尋常，或者說，有點難。事實上，在質數國中的小朋友需要花好幾年來學習加法和減法，但另一方面，乘法及除法對他們來說卻是很容易的。現在你的任務就是幫質數國的人寫一個程式對一個數做"減1"的動作，然後輸出結果。當然，輸入輸出都是以質數國的數字系統來表示（對我們來說也就是因數分解的形式）。

Input

每組測試資料一列，每列有一個X（2 < X <= 32767）的因數分解式。最後一列僅有一個0，代表輸入結束，此列不需輸出。

Output

對每組測試資料輸出一列 X-1 的因數分解式，數字間均有一空白。請參考Sample Output。

Sample Input #1

Sample Output #1

2 4
3 2
13 1 11 1 7 1 5 1 3 1 2 1

C++(失敗版)(一開始想直接用一個string處裡)

/*
17 1 17^1
5 1 2 1 5^1*2^1
509 1 59 1
0
*/

#include <iostream> 
#include <sstream> 
#include <cmath> 
#include <algorithm> 
using namespace std;

void factorization(int n,string s){ //求質因數分解  
	s="";
    int i = 2;
    while( n > 1 )
    {
        int power=0;
        while( n%i == 0 )
        {
        	
            power+=1;
            n = n/i;
        }
        
        if(power>0){
        	//cout<<456;
			s+=to_string(power);
			s+=" ";
			s+=to_string(i);
			s+=" ";
	        
	        
		} 
		i+=1;
		
    }
    reverse(s.begin(),s.end());
    s.erase(0,1);
    cout<<s;
}



int main(){
	string s;
	stringstream ss;
	while(getline(cin,s)){
		if(s=="0")break;
		
		ss.clear();
		ss.str(s);
		int num=1;
		int base_number,power; //底數，次方 
		while(ss>>base_number>>power){
			num*=pow(base_number,power);  //把真實的數字做出來 
		}
		num-=1;
		factorization(num,s);
		cout<<"\n";
		
	}
	return 0;
}

C++

/*
17 1 17^1
5 1 2 1 5^1*2^1
509 1 59 1
0
*/

#include <iostream> 
#include <sstream> 
#include <cmath> 
#include <algorithm> 
#include<vector> 
using namespace std;

string factorization(int n,string s){ //求質因數分解  
	s="";
	vector<int> base_vector,power_vector;
    int i = 2;
    while( n > 1 )
    {
        int power=0;
        while( n%i == 0 )
        {        	
            power+=1;
            n = n/i;
        }
        
        if(power>0){
        	base_vector.push_back(i);
        	power_vector.push_back(power);
		} 
		i+=1;		
    }
    reverse(base_vector.begin(),base_vector.end());
    reverse(power_vector.begin(),power_vector.end());
    for(int j=0;j<base_vector.size();j++){
    	s=s+to_string(base_vector[j])+" "+to_string(power_vector[j])+" ";
	}
	//cout<<s;
	return s;
    
}

int main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	string s;
	stringstream ss;
	while(getline(cin,s)){
		if(s=="0")break;
		
		ss.clear();
		ss.str(s);
		int num=1;
		int base_number,power; //底數，次方 
		while(ss>>base_number>>power){
			num*=pow(base_number,power);  //把真實的數字做出來 
		}
		num-=1;
		s=factorization(num,s);
		cout<<s<<"\n";;
		
	}
	return 0;
}

python: