Prime Land

// File Name: poj1365.cpp  
// Author: bo_jwolf  
// Created Time: 2013骞?0鏈?9鏃?鏄熸湡涓?21:29:25  
  
#include<vector>  
#include<list>  
#include<map>  
#include<set>  
#include<deque>  
#include<stack>  
#include<bitset>  
#include<algorithm>  
#include<functional>  
#include<numeric>  
#include<utility>  
#include<sstream>  
#include<iostream>  
#include<iomanip>  
#include<cstdio>  
#include<cmath>  
#include<cstdlib>  
#include<cstring>  
#include<ctime>  
  
using namespace std;  
vector<int> prime, ans;  
const int maxn = 40000;  
int unprime[ maxn ];  
int main(){  
    unprime[ 0 ] = unprime[ 1 ] = true;  
    for( int i = 2; i < maxn; ++i ){  
        if( !unprime[ i ] ){  
            prime.push_back( i );  
            for( int j = i + i; j < maxn; j += i ){  
                unprime[ j ] = true;  
            }  
        }  
    }  
    int n, p;  
    string line;  
    while( getline( cin, line ),line[ 0 ] != 48 ){  
        ans.clear();  
        istringstream stream( line );  
            long long sum = 1;  
        while( stream >> n >> p ){  
            while( p-- ){  
                sum *= n;  
            }  
        }       sum -= 1;  
        for( int i = prime.size() - 1; i >= 0; --i ){  
            if( sum % prime[ i ] == 0 ){  
                            ans.push_back( prime[ i ] );  
                int temp = 0;  
                while( sum % prime[ i ] == 0 ){  
                    sum /= prime[ i ];  
                    temp++;  
                }  
                ans.push_back( temp );  
            }  
        }  
        for( int i = 0 ; i < ans.size(); ++i ){  
            cout << ans[ i ] << ( i == ans.size() - 1 ?'\n':' ' );  
        }     
    }  
return 0;  
}