Commit | Line | Data |
---|---|---|
6708b7e4 SL |
1 | #ifndef lint |
2 | static char sccsid[] = "@(#)factor.c 4.1 (Wollongong) %G%"; | |
3 | #endif | |
4 | ||
5 | /* | |
6 | * factor [ number ] | |
7 | * | |
8 | * Written to replace factor.s in Bell V7 distribution | |
9 | */ | |
10 | ||
11 | main(argc, argv) | |
12 | char *argv[]; | |
13 | { | |
14 | int n; | |
15 | ||
16 | if (argc >= 2) { | |
17 | sscanf(argv[1], "%d", &n); | |
18 | if (n > 0) | |
19 | printfactors(n); | |
20 | } else { | |
21 | while (scanf("%d", &n) == 1) | |
22 | if (n > 0) | |
23 | printfactors(n); | |
24 | } | |
25 | } | |
26 | ||
27 | /* | |
28 | * Print all prime factors of integer n > 0, smallest first, one to a line | |
29 | */ | |
30 | printfactors(n) | |
31 | register int n; | |
32 | { | |
33 | register int prime; | |
34 | ||
35 | if (n == 1) | |
36 | printf("\t1\n"); | |
37 | else while (n != 1) { | |
38 | prime = factor(n); | |
39 | printf("\t%d\n", prime); | |
40 | n /= prime; | |
41 | } | |
42 | } | |
43 | ||
44 | /* | |
45 | * Return smallest prime factor of integer N > 0 | |
46 | * | |
47 | * Algorithm from E.W. Dijkstra (A Discipline of Programming, Chapter 20) | |
48 | */ | |
49 | ||
50 | int | |
51 | factor(N) | |
52 | int N; | |
53 | { | |
54 | int p; | |
55 | register int f; | |
56 | static struct { | |
57 | int hib; | |
58 | int val[24]; | |
59 | } ar; | |
60 | ||
61 | { register int x, y; | |
62 | ||
63 | ar.hib = -1; | |
64 | x = N; y = 2; | |
65 | while (x != 0) { | |
66 | ar.val[++ar.hib] = x % y; | |
67 | x /= y; | |
68 | y += 1; | |
69 | } | |
70 | } | |
71 | ||
72 | f = 2; | |
73 | ||
74 | while (ar.val[0] != 0 && ar.hib > 1) { | |
75 | register int i; | |
76 | ||
77 | f += 1; | |
78 | i = 0; | |
79 | while (i != ar.hib) { | |
80 | register int j; | |
81 | ||
82 | j = i + 1; | |
83 | ar.val[i] -= j * ar.val[j]; | |
84 | while (ar.val[i] < 0) { | |
85 | ar.val[i] += f + i; | |
86 | ar.val[j] -= 1; | |
87 | } | |
88 | i = j; | |
89 | } | |
90 | while (ar.val[ar.hib] == 0) | |
91 | ar.hib--; | |
92 | } | |
93 | ||
94 | if (ar.val[0] == 0) | |
95 | p = f; | |
96 | else | |
97 | p = N; | |
98 | ||
99 | return(p); | |
100 | } |