Q516: Prime Land

// Run time: 0.320
#include <stdio.h>
void trans(int n);
bool isprime(int n);
int arr[15];

// 因為最大數為32767，所以平方根只要到181就可以了
int p[42]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
             71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,
             149,151,157,163,167,173,179,181};
int main()
{
   int i, j;
   int num;
   int root;
   int prod;
   while (scanf("%d", &root))
   {
       if (!root)  break;
       arr[0] = root;
       for ( i = 1; ; i++)
       {
           scanf("%d", &arr[i]);
           if (getchar() == '\n')
               break;
       }
       num = ++i;
       prod = 1;

       for ( i = 0; i < num; i += 2)
           for ( j = 0; j < arr[i+1]; j++)
               prod *= arr[i];

       prod--; // 減1
       trans(prod);
   }
   return 0;
}

void trans(int n)
{
   if (isprime(n))
   {
       printf("%d 1\n", n);
       return;
   }
   int i, j;
   int cnt;
   bool state = false;

   for ( i = n/2; i >= 2; i--)
   {
       if (!(n%i) && isprime(i))
       {
          cnt = 0;
          while (true)
          {
               if (!(n%i))
               {
                   cnt++;
                   n /= i;
               }
               else
               {
                   if (state)
                       printf(" %d %d", i, cnt);
                   else
                   {
                       printf("%d %d", i, cnt);
                       state = true;
                   }
                   break;
               }
          }
       }
   }
   printf("\n");


}

bool isprime(int n)
{
   int i;
   for ( i = 0; p[i]*p[i] <= n; i++)
       if (!(n%p[i]))
           return false;

   return true;
}