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
48long primes[4800];
49int  num_primes = 2;
50
51static void build_primes (long max);
52void factor (long val, long *fact_list, int fact_size, int *num_fact);
53
54static void
55build_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
85void
86factor(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
115int
116main(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