1 #ifndef lint 2 static char sccsid[] = "@(#)factor.c 4.1 (Wollongong) 06/13/83"; 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 } 101