UVa 516 Solution

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

const int N = 32767;
bool sieve[N];
int prime_time[N][2];

void eratosthenes() {
    // 0 和 1 是質數
    sieve[0] = true;
    sieve[1] = true;

    int sqrt_value = sqrt(N);

    // 找下一個未被刪掉的數字
    for (int i = 2; i <= sqrt_value; i++)
        if (!sieve[i]) {
            // k是倍數，j是質數i的倍數。
            // 由大到小判斷，當sieve[k]成立時，
            // k才能涵蓋所有「大於等於i的質數，其倍數」倍。
            for (int k = (N - 1) / i, j = i * k; k >= i; k--, j -= i)
                if (!sieve[k])
                    sieve[j] = true;
            // 運用小範圍的sieve[k]，避免存取大範圍的sieve[j],
            // 大幅減少cache miss。
        }


}

int main(int argc, char** argv){
    int a,b,total;
    
    eratosthenes();
    
    // 製作質數表
    vector<int> prime;
    for (int i = 1; i < N; i++) {
        if (!sieve[i])
            prime.push_back(i);
    }
  
    string s;

    while(1){
        getline(cin,s);
        
        total=1;
        // check the first number
        // if the first number is 0, get break;
        if(s[0] == '0') {
            break;
        }
        stringstream ss;
        ss.str(s);
        
        while(ss >> a >> b){
            //printf("DEBUG: A=%d, B=%d\n",a,b);
            for(int i=0;i<b;i++){
                total*=a;
            }
            
        }
        
        total -= 1;
        
        //printf("DEBUG:total:%d\n",total);
        
        int hit=0;
        
        bool first=true;
        // 從最大的質數開始找
        int index = prime.size()-1;
        //printf("DEBUG: index initial: %d\n",index);
        while(total < prime[index] && index >= 1) {index--;}
        //printf("DEBUG2: index initial: %d\n",index);
        
        while(index >= 0){
            if(total % prime[index] == 0){
                // if hit, add the hits
                total /= prime[index];
                if(hit == 0) {
                    if(first){
                        first=false;
                    }else{
                        cout << " ";
                    }
                    cout << prime[index];
                }
                hit += 1;
            }else{
                index--;
                if(hit > 0){
                    cout << " " << hit;
                    hit=0;
                }
            }
        }
        cout<<"\n";
         
    }
}