/* NNFactoring.c */
/* Factor any number 1 < N < 2 147 483 648 = 2^31 into powers of primes */

/* note PrimeFactors[NN32] contains all natural number primes <= 46337;
   note PrimeFactors[NN32-1] = 46337 <= 46340, 46341*46341 rollover */

#include <stdio.h>
#define NN32 4793           /* Primefactors[4791] = 46337 */
#define MM 51
#define MAXINT 2147483647

#include "..\\SubProgs\\GenLowerPrimes.c"
#include "..\\SubProgs\\GetPrimeFactors.c"

void GenLowerPrimes(int*);
int GetPrimeFactors(int*,int*,int*,int);


void main(void)
{
 int I,K,N,
   LowPrimes[NN32],PrimeFactors[NN32],Exponents[NN32];

 GenLowerPrimes(LowPrimes);

 puts("This program lists all the prime factors of a given natural number");
  printf("  between 2 and %d  or input zero to terminate program\n\n",MAXINT);

LP:
 scanf("%d",&N); getchar();
 if (!N) goto FIN;
 if (N<=1)
  {puts("Please input zero to terminate, or a natural number > 1"); goto LP;}

 K=GetPrimeFactors(LowPrimes,PrimeFactors,Exponents,N);
/* printf("K=%d PrimFac0=%d Exp0=%d\n",K,PrimeFactors[0],Exponents[0]); */

 if ((K<2) && (Exponents[0]<2))
  {
   printf("%d is a prime\n",N);
   puts("\nInput zero or natural number");
   goto LP;
  }
 printf("%d  =  ",N);
 for (I=0; I<K-1; I++)
  if (Exponents[I]>1) printf("%d^%d x ",PrimeFactors[I],Exponents[I]);
  else printf("%d x ",PrimeFactors[I]);
 I=K-1;
 if (Exponents[I]>1) printf("%d^%d\n",PrimeFactors[I],Exponents[I]);
 else printf("%d\n",PrimeFactors[I]);

 puts("\nInput zero or natural number");
 goto LP;
FIN:
}