/* Copyright (c) 2008 Anonymous
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that you grant this
 * same permission to anyone you distribute it to without any additional
 * restrictions.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stdio.h>

#include <gmp.h>

void print_factors(mpz_t num, char *separator){
 mpz_t i, sqr;
 mpz_init(sqr);
 mpz_sqrt(sqr, num);
 for(mpz_init_set_ui(i, 2); mpz_cmp(i, sqr) <= 0; mpz_nextprime(i, i)){
  unsigned long int count = mpz_remove(num, num, i);
  if(count) mpz_sqrt(sqr, num);
  for(; count > 0; --count){
   mpz_out_str(stdout, 10, i);
   fputs(separator, stdout);
  }
 }
 mpz_clear(i);
 mpz_clear(sqr);
 if(mpz_cmp_ui(num, 1)) mpz_out_str(stdout, 10, num);
 puts("");
}

int main(int argc, char *argv[]){
 mpz_t num;
 mpz_init(num);
 for(int i = 1; i < argc; ++i){
  mpz_set_str(num, argv[i], 0);
  if(mpz_sgn(num) > 0) print_factors(num, " ");
 }
 mpz_clear(num);
 return 0;
}