/* Program to take a list of factors of googolplex+10, 
   and split it into canonical 2*k*d+1 form, 
   where d is a product of unique prime factors of 10^100+1
*/

#include <stdio.h>
#include <gmp.h>
#include <stdlib.h>
#include <ctype.h>

static char const *factors[17]=
{
    "11","41","101","251","271","3541","5051","9091",
    "21401","25601","27961","60101","7019801",
    "182521213001","14103673319201","78875943472201","1680588011350901"
};

static mpz_t gsmalls[17];

/*
static int numbigs;
static int bigs[30000];
static mpz_t gbigs[30000];
*/

int main()
{
    char buffer[1000];
    mpz_t in, div, rem;

    int i;
    for(i=0; i<17; ++i)
    {
	mpz_init_set_str(gsmalls[i], factors[i], 10);
    }
    
    mpz_init(in);
    mpz_init(div);
    mpz_init(rem);

    while(fgets(buffer, 1000, stdin))
    {
	int numthrees=0;
	int flags=0;

	if(!isdigit(buffer[0]))
	{
	    printf("ignoring: %s", buffer);
	    continue;
	}
	/* get the number */
	mpz_set_str(in, buffer, 10);
	
	/* debug - progress */
	mpz_out_str(stdout, 10, in);

	/* q=2*(D*k)+1, so first strip the +1 and the 2* */
	mpz_sub_ui(in, in, 1);
	mpz_tdiv_q_2exp(in, in, 1);

	/* count the threes (up to two of them) */
	mpz_tdiv_qr_ui(div, rem, in, 3);
	if(!mpz_sgn(rem)) 
	{ 
	    ++numthrees; 
	    mpz_set(in, div);
	    mpz_tdiv_qr_ui(div, rem, in, 3);
	    if(!mpz_sgn(rem)) 
	    { 
		++numthrees; 
		mpz_set(in, div);
	    }
	}
	printf(" = 2* ( 3^%i", numthrees);
	
	/* count the small factors */
	for(i=0; i<17; ++i)
	{
	    mpz_tdiv_qr(div, rem, in, gsmalls[i]);
	    if(!mpz_sgn(rem)) 
	    { 
		flags|=(1<<i);
		mpz_set(in, div);
		printf(" %s", factors[i]);
	    }
	}

	/* what's left over? */
	printf(" * ");
	mpz_out_str(stdout, 10, in);
	printf(" ) +1\n");
    }
    return 0;
}