/*----------------------------------------------------------------------
  File    : pfacts.c
  Contents: determine the prime factors of a given number
  Author  : Christian Borgelt
  History : 17.11.1997 file created
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

void pfacts (int n)
{                               /* --- determine prime factors of n */
  int d;                        /* divisor to try */
  int i;                        /* increment of divisor */
  int e;                        /* exponent of a prime factor */

  if (n <= 1) return;           /* 1 does not have any prime factors */
  printf("%d =", n);            /* print the number to work on */
  if (n % 2 == 0) {             /* if m is even, */
    e = 0;                      /* then 2 is a prime factor */
    do { e++; n /= 2; } while (n % 2 == 0);
    printf(" 2^%d", e);         /* divide out prime factor 2 */
  }                             /* and print its exponent */
  if (n % 3 == 0) {             /* if m is divisible by 3, */
    e = 0;                      /* then 3 is a prime factor */
    do { e++; n /= 3; } while (n % 3 == 0);
    printf(" 3^%d", e);         /* divide out prime factor 3 */
  }                             /* and print its exponent */
  for (d = 5, i = 2; d*d <= n; d += i, i ^= 6) {
    if (n % d == 0) {           /* if m is divisible by d, */
      e = 0;                    /* then d is a prime factor */
      do { e++; n /= d; } while (n % d == 0);
      printf(" %d^%d", d, e);   /* divide out prime factor d */
    }                           /* and print its exponent */
  }
  if (n > 1)                    /* if n still contains a factor, */
    printf(" %d^1", n);         /* print the last prime factor */
  printf("\n");                 /* terminate output line */
}  /* pfacts() */

/*----------------------------------------------------------------------
There is not much to be said about the above function. The trick used
to speed up the divisor tests has already been explained in the program
`prime.c'. Test the 2 and the 3 before the loop and in the loop skip
multiples of 2 and 3. There are only two things that may require some
additional explanation.
  The first is: In the loop, we only skip multiples of two and three.
Hence we sometimes try a non-prime number as a divisor. Why do we end
up with only prime numbers as factors? This is due to the fact that we
divide out all prime factors found. For example, let n = 21025 = 5^2 *
29^2. This number is divisible by 25. 25 is not divisible by 2 or by 3
and is thus tested as a divisor in the loop. Hence, at first glance, one
may think that 25 should appear as a factor. But this is not the case,
since before we reach d = 25 and test it, we already found that n is
divisible by 5 and divided out this prime factor. That is, when we try
d = 25, it is n = 841 = 29^2, which is not divisible by 25 and thus 25
is skipped. It is easily verified that the factors of any non-prime
number are divided out before this number is tried as a divisor, and
thus no non-prime number is printed as a factor.
  The second is: Why do we need this extra test on n > 1 after the loop?
This is due to the fact that we stop the loop, if d*d > n. In this case
the last prime factor, if it has exponent 1, is not divided out from n.
Take n = 14 as an example. The loop is terminated with d = 5 and n = 7.
If we did not check for n > 1, we would fail to notice the factor 7.
----------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int n;                        /* number to split */

  if (argc != 2) {              /* if wrong number of arguments given */
    printf("usage: %s n\n", argv[0]);
    printf("split n into prime factors\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the function */
  n = atoi(argv[1]);            /* convert argument to a number */
  if (n <= 1) {                 /* check for a correct argument */
    printf("%s: illegal number\n", argv[0]); return 1; }
  pfacts(n);                    /* determine prime factors */
  return 0;                     /* return 'ok' */
}  /* main() */

/*----------------------------------------------------------------------
Nothing new here. Just standard command line evaluation and a call to
the function that does the work.
----------------------------------------------------------------------*/