/* ComputeLCM.c */

#include <stdio.h>
#define NN32 4793           /* Primefactors[4791] = 46337 */
#define MM 51
#define MAXINT 2147483647
#define MAXint 46340        /* 46341*46341 causes rollover (32 bit integers) */
#define INF 0X8FFFFF

#include "..\\SubProgs\\GenLowerPrimes.c"
#include "..\\SubProgs\\GetPrimeFactors.c"
#include "..\\SubProgs\\ProdPrimestoNum.c"
#include "..\\SubProgs\\GCD.c"
#include "..\\SubProgs\\MAX.c"

void GenLowerPrimes(int*);
int GetPrimeFactors(int*,int*,int*,int);
void PrintProdPrimes(int*,int*);
int LCM1(int,int);
int LCM2(int,int,int*,int*,int*);
int MAX(int,int);

void main(void)
{
 int K,N1,N2,   LowPrimes[NN32],PrimeFactors[NN32],Exponents[NN32];

 GenLowerPrimes(LowPrimes);

 puts("This program computes the least common multiple (LCM)");
 printf("Input two natural numbers between 1 and %d, separated by commas\n",
             MAXint);
 puts("(Input two zeros to terminate program)\n");

LP:
 puts("Input the two numbers separated by a comma");

 scanf("%d,%d",&N1,&N2); getchar();
 if ((!N1)&&(!N2)) goto FIN;
 if ((N1<=0)||(N2<=0))
  {puts("Please do not use negative numbers or a single zero"); goto LP;}



  
 K=LCM1(N1,N2);
 if (K) printf("LCM(%d,%d)=%d\n\n",N1,N2,K);
 else  
  {
   LCM2(N1,N2,LowPrimes,PrimeFactors,Exponents);
   PrintProdPrimes(PrimeFactors,Exponents);
  } 
 
 goto LP;

FIN:
}

/*****************************************************************/
int LCM1(N1,N2)
{
 int H,K;

 H=N1%N2; if (!H) return N1;  H=N2%N1; if (!H) return N2;
 H=GCD(N1,N2);       
 if (N1<N2) {K=N2/H; if ((N1 < MAXint) && (K < MAXint)) return (N1*K);}
 K=N1/H; if ((K < MAXint) && (N2 < MAXint)) return (K*N2);

 /* arrive here if LCM(N1,N2) too large for system */
 return 0;  /* flag to use primefactors-exponents form in LCM2 */
}

/*****************************************************************/

int LCM2(int N1, int N2, int *LowP, int *PF, int *EF)
{
 int K1,K2,CNT=0, *PF1,*PF2,*EF1,*EF2,
     PrimeFactors1[NN32],Exponents1[NN32],
     PrimeFactors2[NN32],Exponents2[NN32];

  PF1=PrimeFactors1; EF1=Exponents1; PF2=PrimeFactors2; EF2=Exponents2;

 K1=GetPrimeFactors(LowP,PF1,EF1,N1);
 K2=GetPrimeFactors(LowP,PF2,EF2,N2);

 PF1[K1]=PF2[K2]=INF;

LP:
   while (*PF1<*PF2) {*PF=*PF1; *EF=*EF1; PF++; EF++; PF1++; EF1++; CNT++;}
   while (*PF1>*PF2) {*PF=*PF2; *EF=*EF2; PF++; EF++; PF2++; EF2++; CNT++;}

 /* arrive here if *PF1=*PF2 */
   if (*PF1!=INF)
    {*PF=*PF1; *EF=MAX(*EF1,*EF2); PF++; EF++; PF1++; EF1++; PF2++; EF2++;
     goto LP;}

 /* arrive here if *PF1 = *PF2 = INF */
   *PF=*EF=0;     /* end of data markers */
 return CNT;
}

/*****************************************************************/

void PrintProdPrimes(int *PF, int *EF)
{
 if(*PF) {printf("%d",*PF); if (*EF>1) printf("^%d",*EF); PF++; EF++;}
 else {puts("No number"); return;}

 while (*PF)
  {
   printf(" x ");
   printf("%d",*PF); if (*EF>1) printf("^%d",*EF);
   PF++; EF++;
  }
 puts("\n"); 
 return;
}   

/*
 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]);

 goto LP;
FIN:
}

int LCMint(int N1, int N2)    no rollover; return integer
{
 int H,K;

 if (N1==1) return N2;
 if (N2==1) return N1;
 if (N1==N2) return N1;
*/