#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[]) {
  int a;
  while(1) {
    int inp = scanf("%d", &a);

    if (a < 0 || inp != 1) {
      fprintf(stderr, "Error: Chybny vstup!\n");
      return 100;
    }

    // end of input
    if (a == 0)
      break;


    printf("Prvociselny rozklad cisla %d je:\n", a);

    if (a == 1) {
      printf("1\n");
      continue;
    }

    // counting factors that are two
    int count = 0;
    while (a % 2 == 0) {
      count++;
      a /= 2;
    }

    if (count == 1) {
      printf("%d", 2);
    } if (count > 1) {
      printf("2^%d", count);
    }

    if (a == 1) {
      printf("\n");
      continue;
    } else if (count > 0) {
      printf(" x ");
    }

    // looking for all the odd prime factors
    for (int i = 3; i <= a/2; i += 2) {

      count = 0;
      while (a % i == 0) {
        count++;
        a /= i;
      }

      if (count == 1)
        printf("%d", i);
      else if (count > 1)
        printf("%d^%d", i, count);

      if (a == 1) {
        printf("\n");
        break;
      } else if (count > 0) {
        printf(" x ");
      }
    }

    if (a != 1) {
      printf("%d\n", a);

    }
  }

  return 0;
}