#include <stdio.h>
#include <stdlib.h>
int checkIfPrime(int x);
int checkIfPalindrome(int x);
int extractPrimeFactors(int a[],int num);
void permutate(int a[],int lastIndex,int number);
int checkedAndPrinted[100],in;
int main()
{
  int array[100],n,i;
  in=0;
  for(i=0;i<100;i++)
  {
    array[i] = -1;
    checkedAndPrinted[i] = -1;
  }
  printf("Enter the number ");
  scanf("%d",&n);
  int lastIndex = extractPrimeFactors(array,n);
  permutate(array,lastIndex,0);
  
  printf("\n");
  
  return 0;
}
int checkIfPrime(int x)
{
  if(x==1)
    return 0;
  int i=0;
  int isPrime = 1;
  for(i=2;i<= x/2;i++)
  {
    if(x%i==0)
    {
      isPrime = 0;
      return isPrime;
    }
  }
  return isPrime;
}
int checkIfPalindrome(int x)
{
    int n = x;
    int sum = 0;
    while(n > 0)
    {
	int digit = n%10;
	n = n/10;
	sum = sum*10 + digit;
    }
    if(sum == x)
    {
      return 1;
    }
    else
      return 0;

}
int extractPrimeFactors(int a[],int num)
{
  int i=0,n=num,index=0;
  for(i=1;i<num;i++)
  {
    if(checkIfPrime(i))
    {
      while(n%i == 0)
      {
	printf("Adding %d to List of prime factors \n",i);
	a[index++] = i;
	n = n/i;
      }
    }
  }
  //printf("last index = %d \n",index);
  return index-1;
}
void permutate(int a[],int lastIndex,int number)
{
  int i=0,ch=0,j=0,ch1=0;
  for(i=0;i<=lastIndex;i++)
  {
    if(a[i] != -1)
      ch=1;
  }
  if(ch == 0)
  {
    // check if number is palindrome and return
    //printf("checking number %d\n",number);
    if(checkIfPalindrome(number))
    {
      //printf("Palindorme found: %d \n",number);
      for(j=0;j<in;j++)
      {
	if(checkedAndPrinted[j] == number)
	  ch1=1;
      }
      if(ch1 != 1)
      {
	printf("Palindromic permutation is %d\n",number);
	checkedAndPrinted[in++] = number;
      }
    }
    return;
  }
  for(i=0;i<=lastIndex;i++)
  {
    if(a[i]== -1)
      continue;
    
    //printf("number %d   a[i] %d \n",number,a[i]);
    int temp = a[i];
    a[i] = -1;   // this step ensures that a prime number used in this step is not used in any recursive step in any child step
    
    if(temp < 10)
    {
      permutate(a,lastIndex,number*10+temp);
    }
    if(temp > 10 && temp < 100)
    {
      permutate(a,lastIndex,number*100+temp);
    }
    if(temp > 100 && temp < 1000)
    {
      permutate(a,lastIndex,number*1000+temp);
    }
    a[i] = temp;    // this step ensures that a prime number used in this step is available for use in any sibling branch's step
  }
}