#include <iostream>#include <stdio.h>#include <memory.h>#include <cmath>using namespace std;#define inf 2000000000struct node{ int num; char s[100];}a[20010];void ini(){ int i,now,j,tem,cnt; for(i=1;i<=20000;i++) a[i].num=inf; a[1].num=1; strcpy(a[1].s,"1"); a[2].num=1; strcpy(a[2].s,"2"); a[3].num=1; strcpy(a[3].s,"3"); a[5].num=1; strcpy(a[5].s,"5"); a[7].num=1; strcpy(a[7].s,"7"); a[4].num=2; strcpy(a[4].s,"(2^2)"); a[6].num=1; strcpy(a[6].s,"3!"); a[24].num=2; strcpy(a[24].s,"(2^2)!"); a[120].num=1; strcpy(a[120].s,"5!"); a[720].num=1; strcpy(a[720].s,"3!!"); a[5040].num=1; strcpy(a[5040].s,"7!"); for(now=4;now<=20000;now++) { if(a[now].num!=inf) continue; tem=(int)sqrt(now+0.0); for(i=2;i<=tem;i++) { if(now%i==0) { j=now/i; if(a[i].num+a[j].num<a[now].num) { a[now].num=a[i].num+a[j].num; strcpy(a[now].s,"("); strcat(a[now].s,a[i].s); strcat(a[now].s,"*"); strcat(a[now].s,a[j].s); strcat(a[now].s,")"); } cnt=now; j=0; while(cnt%i==0&&cnt>0) { ++j; cnt/=i; } if(cnt==1) { if(a[i].num+a[j].num<a[now].num) { a[now].num=a[i].num+a[j].num; strcpy(a[now].s,"("); strcat(a[now].s,a[i].s); strcat(a[now].s,"^"); strcat(a[now].s,a[j].s); strcat(a[now].s,")"); } } } } for(i=1;i<=now/2;i++) { j=now-i; if(a[i].num+a[j].num<a[now].num) { a[now].num=a[i].num+a[j].num; strcpy(a[now].s,"("); strcat(a[now].s,a[i].s); strcat(a[now].s,"+"); strcat(a[now].s,a[j].s); strcat(a[now].s,")"); } } }}int main(){ ini(); int n; while(scanf("%d",&n)!=EOF) { printf("%sn",a[n].s); } return 0;}
