#include "stdio.h"
#include "malloc.h"
#include "math.h"
#define LEN sizeof(struct prime)
#define NULL 0

struct prime
{int pri;
 int num;
 struct prime *next;
};

int power(int n,int m)/*求幂*/
{
  int i,s=1;
  for(i=1;i<=m;i++) s*=n;
  return s;
}

int prime(int n)/*判断素数*/
{
  int i;
  if(n==1) return 0;
  else{
  for(i=2;i<=sqrt(n);i++) {if(n%i==0) break;}
  if(i>sqrt(n)) return 1;
  else return 0;}
}

int product(struct prime *head,int i)/*求链表已建立部分除去最后一个节点的乘积*/
{
  int pro=1;
  struct prime *p=head;
  for(;p->pri<i;p=p->next)
  pro*=power(p->pri,p->num);
  return pro;
}

struct prime *decompose(int composite)/*建立链表*/
{
  struct prime *head,*p1,*p2;
  int i,n=composite;
  i=2;
  while(i<composite/2)/*求出第一个节点*/
 {
   if(prime(i) && (composite%i==0))
   {
      head=p1=p2=(struct prime *)malloc(LEN);
      p1->pri=i;p1->num=0;
      while(n%i==0)
      {p1->num++;n/=i;}
      break;
    }
    if(i==2) i+=1;else i+=2;
  }
  if(power(p1->pri,p1->num)!=composite)
  for(i=p1->pri+((p1->pri==2)?1:2);i<=composite/2;i+=2)
  {
    if(prime(i) && (composite%i==0))
    {
      n=composite;
      p1=(struct prime *)malloc(LEN);
      p1->pri=i;
      p1->num=0;
      while(n%i==0) {p1->num++;n/=i;}
      p2->next=p1;
      p2=p1;
      if(p1->num)/*当所求的素数和他的幂足以分解所给合数时停止*/
      {if(product(head,i)*power(p1->pri,p1->num)==composite) break;}  
     }
  }
  p2->next=NULL;
  return head;
}

void main()
{
   int composite;
   struct prime *p;
   scanf("%d",&composite);
   if(prime(composite))
   printf("This is a prime number.\n");
   else
   {
     printf("The way of decomposing the composite is(prime number with its power):\n");
     p=decompose(composite);
     do
       {printf("%d^%d  ",p->pri,p->num);
        p=p->next;
       }while(p!=NULL);
   }
}