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

void facs(unsigned long long int);

int main(int argc, char **argv)
{
  int i;
  unsigned long long int number;
  for (i = 1; i < argc; i++) {
    number = strtoull(argv[i], NULL, 10);
    facs(number);
  }
  return 0;
}

void facs(unsigned long long int number)
{
  int i = 0;
  unsigned long long int factors[64], factor = 2, orignum = number;
  if (number < 2) {
    printf("%llu: n/a\n", orignum);
    return;
  }
  while (factor <= (sqrt(number) + 1)) {
    if (number % factor == 0) {
      factors[i++] = factor;
      number /= factor;
    } else {
      factor++;
    }
  }
  if (number != 1) factors[i++] = number;
  factors[i] = 0;
  printf("%llu: ", orignum);
  i = 0;
  if (orignum == number)
    printf("prime");
  else
    while (factors[i])
      printf("%llu ", factors[i++]);
  printf("\n");
  return;
}