104 lines
1.4 KiB
C
104 lines
1.4 KiB
C
#ifndef lint
|
|
static char sccsid[] = "@(#)factor.c 1.1 92/07/30 SMI"; /* from UCB 4.1 06/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);
|
|
}
|
|
|
|
exit(0);
|
|
/* NOTREACHED */
|
|
}
|
|
|
|
/*
|
|
* 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);
|
|
}
|