#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <fstream.h>
#include <string.h>
typedef struct nod
{unsigned long n;
 nod *urm;
}*PNOD;
PNOD prim=NULL,ultim=NULL;

void invers(char a[],char x[])
{for (int i=0;i<strlen(a);i++)
 {x[strlen(a)-i-1]=a[i];}
 x[strlen(a)]=NULL;
}

void scadere(char a[],char b[],char s[])
{int lb=strlen(b),la=strlen(a);
 int i=0,c=0;
 while(i<lb)
 {s[la-i-1]=a[la-i-1]-b[lb-i-1]-c+48;
  if(s[la-i-1]<48){s[la-i-1]+=10;c=1;}
  else{c=0;}
  i++;
 }
 while(i<la)
 {s[la-i-1]=a[la-i-1]-c;
  i++;
  c=0;
 }
 s[i]='\0';

}

void suma( char a[], char b[], char x[],int off)
{char ia[60],ib[60],s[60];
 invers(a,ia);
 invers(b,ib);
 int la=strlen(a),lb=strlen(b),i=0,c=0;
 while(i<off)
 {s[i]=ia[i];
  i++;
 }
   i=0;
 while(i+off<la&&i<lb)
 {
  s[i+off]=ia[i+off]+ib[i]+c-48;
  if(s[i+off]>57)
  {s[i+off]-=10;c=1;}
  else
  {c=0;}
  i++;
 }

 while(i+off<la)
 {s[i+off]=ia[i+off]+c;
  if(s[i+off]>57){s[i+off]-=10;c=1;}
  else{c=0;}
  i++;
 }
 while(i<lb)
 {s[i+off]=ib[i]+c;
  if(s[i+off]>57){s[i+off]-=10;c=1;}
  else{c=0;}
  i++;
 }


 if(c==1)
 {s[i+off]=49;s[i+1+off]='\0';}
 else{s[i+off]='\0';}
 invers(s,x);

}

void produs (char a[],char b[],char p[])
{char ia[60],ib[60],aux[60]="0",aux2[60];
 int i,j;
 strcpy(p,"0");
 invers(a,ia);
 invers(b,ib);
 int li=strlen(ia),lb=strlen(ib),c=0;
 for (i=0;i<li;i++)
 {c=0;
  for(j=0;j<lb;j++)
  {aux[j]=((ia[i]-48)*(ib[j]-48)+c)%10+48;
   c=((ia[i]-48)*(ib[j]-48)+c)/10;
  }
  if(c!=0)
  {aux[j]=c+48;aux[j+1]='\0';}
  else{aux[j]='\0';}

  invers(aux,aux2);
  suma(p,aux2,aux,i);
  strcpy(p,aux);
//  cout<<aux<<"  "<<aux2<<endl;
 }
}
void adauga(unsigned long n)
{PNOD q=new nod;
 if(!prim)
 {prim=q;}
 else
 {ultim->urm=q;}
 q->urm=NULL;
 q->n=n;
 ultim=q;
}

void calculeazaNumerePrime(long n)
{PNOD p;
 long i;
 int sw;
 adauga(2);
 for (i=3;i<n;i+=2)
 {sw=0;
  for (p=prim->urm;p!=NULL&&sqrt(i)>=p->n;p=p->urm)
  {if(i%p->n==0)
   {sw=1;
    break;
   }
  }
  if(sw==0)
  {adauga(i);}
 }
}

int main ()
{PNOD p,q;
  long n;
 int k;
 clrscr();
 ifstream f("prim.in");
 f>>n;
 calculeazaNumerePrime(n/2+1);
 char sir[60]="0",aux[60],aux2[60],aux3[60],fin[60],*final;
 ltoa(n,aux,10);
 produs(aux,aux,fin);

 for(p=prim;p!=NULL;p=p->urm)
 {if(n/p->n>1)
  {ltoa(n/p->n,aux,10);
   cout <<n/p->n<<" ";
   scadere(aux,"1",aux2);
   produs(aux,aux2,aux3);

   scadere(fin,aux3,aux);
   strcpy(fin,aux);
  }
  else if(n/p->n)
  {scadere(fin,"1",aux);
   strcpy(fin,aux);
  }

 }
 ltoa(n-1,aux,10); scadere(fin,aux,aux2); strcpy(fin,aux2);

 ofstream fout("prim.out");
 final=fin;
 while(*final=='0'){final++;}
 fout <<final;
 fout.close();
 return 0
}