BSD 4_3 release

[unix-history] / usr / src / games / factor.c

#ifndef lint
static char sccsid[] = "@(#)factor.c    4.1 (Wollongong) 6/13/83";
#endif

/*
*              factor [ number ]
*
* Written to replace factor.s in Bell V7 distribution
*/

main(argc, argv)
char    *argv[];
{
       int     n;

       if (argc >= 2) {
               sscanf(argv[1], "%d", &n);
               if (n > 0)
                       printfactors(n);
       } else {
               while (scanf("%d", &n) == 1)
                       if (n > 0)
                               printfactors(n);
       }
}

/*
* Print all prime factors of integer n > 0, smallest first, one to a line
*/
printfactors(n)
       register int    n;
{
       register int    prime;

       if (n == 1)
               printf("\t1\n");
       else while (n != 1) {
               prime = factor(n);
               printf("\t%d\n", prime);
               n /= prime;
       }
}

/*
* Return smallest prime factor of integer N > 0
*
* Algorithm from E.W. Dijkstra (A Discipline of Programming, Chapter 20)
*/

int
factor(N)
       int     N;
{
       int             p;
       register int    f;
       static struct {
               int     hib;
               int     val[24];
       } ar;

       {       register int    x, y;

               ar.hib = -1;
               x = N; y = 2;
               while (x != 0) {
                       ar.val[++ar.hib] = x % y;
                       x /= y;
                       y += 1;
               }
       }

       f = 2;

       while (ar.val[0] != 0 && ar.hib > 1) {
               register int    i;

               f += 1;
               i = 0;
               while (i != ar.hib) {
                       register int    j;

                       j = i + 1;
                       ar.val[i] -= j * ar.val[j];
                       while (ar.val[i] < 0) {
                               ar.val[i] += f + i;
                               ar.val[j] -= 1;
                       }
                       i = j;
               }
               while (ar.val[ar.hib] == 0)
                       ar.hib--;
       }

       if (ar.val[0] == 0)
               p = f;
       else
               p = N;

       return(p);
}