/* ListofPrimeFacts.c */
/* List of all prime factors of any natural number N<2 147 483 648 = 2^31 - 1 */
/* note A[NN] contains the largest consecutive prime in array A
   note A[NN] = 46337 <= 46340, 46341*46341 rollover */
#include <stdio.h>
#define NN 4792
#define MAXINT 2147483647
void GENPRIMES(int*);

void main(void)
{
 int I,K,N,P,LastPrime,NumFactors,EXP,A[NN];             /* P = Prime */

 GENPRIMES(A);   LastPrime=A[NN-1];
 puts("This program lists all the prime factors of a given natural number");
 printf("Input zero to terminate program, or a natural number <= %d\n",MAXINT);

AGAIN:
  scanf("%d",&N); getchar();
 if (!N) goto FIN2;
 if (N==1) {printf("No prime factors"); goto FIN;}
 K=N;
 I=0; P=A[0];  NumFactors=1;    printf("List of prime factors:  ");
LP:
 EXP=0;
 while (!(K%P)) {EXP++; K/=P; NumFactors++;}
 if (EXP==1) printf("%d ",P);
 if (EXP>1) printf("%d ",P);
 if (K==1) goto FIN;
 I++; P=A[I];
 if (I<NN) goto LP;

 if (K>LastPrime) {printf("%d",K); NumFactors++;}

FIN:
 if (NumFactors==2) printf(" (prime)\n");
 puts("\n");
 goto AGAIN;
FIN2:
}

void GENPRIMES(int* A) /* generate the first NN primes in A */
{
 int I,J,K,K12,ODD;

 A[0]=2; A[1]=3; I=2; K=2; K12 = 9; ODD=3;

 LP:
   ODD += 2;
   if (K12<=ODD) {K++; K12=(K+1)*(K+1);} /* adjust K so that K<=SQRT(ODD)<K+1 */
   for (J=1; A[J]<=K; J++)        /* see if any primes div ODD */
     if (!(ODD%A[J])) goto LP;
   A[I]=ODD; I++;                 /* to place the next prime in A[I] */
   if (I<NN) goto LP;
}