| 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 | } |