1 /* $NetBSD: factor.c,v 1.2 2021/01/31 20:51:04 rillig Exp $ */
2
3 /*
4 * Copyright 1997 Piermont Information Systems Inc.
5 * All rights reserved.
6 *
7 * Written by Philip A. Nelson for Piermont Information Systems Inc.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. The name of Piermont Information Systems Inc. may not be used to endorse
18 * or promote products derived from this software without specific prior
19 * written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY PIERMONT INFORMATION SYSTEMS INC. ``AS IS''
22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL PIERMONT INFORMATION SYSTEMS INC. BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
31 * THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 */
34
35 #include <sys/cdefs.h>
36 #include <stdio.h>
37
38
39 /*
40 * primes - prime table, built to include up to 46345 because
41 * sqrt(2^31) = 46340.9500118415
42 *
43 * building the table instead of storing a precomputed table saves
44 * about 19K of space on the binary image.
45 */
46
47 #ifdef TESTING
48 long primes[4800];
49 int num_primes = 2;
50
51 static void build_primes (long max);
52 void factor (long val, long *fact_list, int fact_size, int *num_fact);
53
54 static void
build_primes(long max)55 build_primes(long max)
56 {
57 long pc;
58 int j;
59 long rem;
60
61 /*
62 * Initialise primes at run-time rather than compile time
63 * so it's put in bss rather than data.
64 */
65 primes[0] = 2;
66 primes[1] = 3;
67
68 for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) {
69 j = 0;
70 rem = 1;
71 while (j < num_primes && primes[j] * primes[j] <= pc) {
72 if ((rem = pc % primes[j]) == 0)
73 break;
74 j++;
75 }
76 if (rem)
77 primes[num_primes++] = pc;
78 }
79 }
80
81 /* factor: prepare a list of prime factors of val.
82 The last number may not be a prime factor if the list is not
83 long enough. */
84
85 void
factor(long val,long * fact_list,int fact_size,int * num_fact)86 factor(long val, long *fact_list, int fact_size, int *num_fact)
87 {
88 int i;
89
90 /* Check to make sure we have enough primes. */
91 build_primes(val);
92
93 i = 0;
94 *num_fact = 0;
95 while (*num_fact < fact_size-1 && val > 1 && i < num_primes) {
96 /* Find the next prime that divides. */
97 while (i < num_primes && val % primes[i] != 0) i++;
98
99 /* Put factors in array. */
100 while (*num_fact < fact_size-1 && i < num_primes &&
101 val % primes[i] == 0) {
102 fact_list[(*num_fact)++] = primes[i];
103 val /= primes[i];
104 }
105 }
106 if (val > 1)
107 fact_list[(*num_fact)++] = val;
108 }
109
110
111
112 #include <stdio.h>
113 #include <stdlib.h>
114
115 int
main(int argc,char ** argv)116 main(int argc, char **argv)
117 {
118 long facts[30];
119 long val;
120 int i, nfact;
121 int arg;
122
123 if (argc < 2) {
124 fprintf (stderr, "usage: %s numbers\n", argv[0]);
125 exit(1);
126 }
127
128 /* Factor each arg! */
129 for (arg = 1; arg < argc; arg++) {
130
131 val = atol(argv[arg]);
132 factor (val, facts, 30, &nfact);
133
134 printf ("%ld:", val);
135 for (i = 0; i<nfact; i++)
136 printf (" %ld", facts[i]);
137 printf ("\n");
138
139 }
140
141 return 0;
142 }
143 #endif
144