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

uintmax_t isqrt(uintmax_t n){
 uintmax_t r = 0;
 // fixed this so it should work even if uintmax_t is an odd number of bits!
 // ... i've never seen an implementation where that's the case, but i realized
 // that the code i had here before would break if someone was perverse enough
 // to do that, so i fixed it.
 for(uintmax_t i = ~(UINTMAX_MAX >> 2) & UINTMAX_MAX / 3; i; i >>= 2)
  if(n >= (i | r)){
   n -= i | r;
   r = r >> 1 | i;
  } else r >>= 1;
 return r;
}

void printfactors(uintmax_t n, char *separator){
 while(n != 2 && !(n % 2)){
  n >>= 1;
  printf("%ju%s", 2, separator);
 }
 while(n != 3 && !(n % 3)){
  n /= 3;
  printf("%ju%s", 3, separator);
 }
 for(uintmax_t i = 5, s = 2; i <= isqrt(n); i += 2 + (s ^= 2))
  while(n != i && !(n % i)){
   n /= i;
   printf("%ju%s", i, separator);
  }
 printf("%ju", n);
}

int main(int argc, char* argv[]){
 int size=ceil(log10(INTMAX_MAX))+1;
 char str[size];
 for(int i = 1; i < argc || (argc == 1 && !feof(stdin)); ++i){
  intmax_t n = strtoimax(argc == 1 ? (fgets(str, size, stdin), str) : argv[1],
   NULL, 0);
  printf("prime factors of %ju: ", n);
  printfactors(n, " ");
  puts("");
 }
 return 0;
}