1/*	$NetBSD: factor.c,v 1.13 2011/04/04 08:30:12 mbalmer 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/* Prototypes for strict prototyping. */
36
37#include <sys/cdefs.h>
38
39#include <stdio.h>
40
41
42/*
43 * primes - prime table, built to include up to 46345 because
44 * sqrt(2^31) = 46340.9500118415
45 *
46 * building the table instead of storing a precomputed table saves
47 * about 19K of space on the binary image.
48 */
49
50#ifdef TESTING
51long primes[4800];
52int  num_primes = 2;
53
54static void build_primes (long max);
55void factor (long val, long *fact_list, int fact_size, int *num_fact);
56
57static void
58build_primes(max)
59	long max;
60{
61	long pc;
62	int j;
63	long rem;
64
65	/*
66	 * Initialise primes at run-time rather than compile time
67	 * so it's put in bss rather than data.
68	 */
69	primes[0] = 2;
70	primes[1] = 3;
71
72	for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) {
73		j = 0;
74		rem = 1;
75		while (j < num_primes && primes[j] * primes[j] <= pc) {
76			if ((rem = pc % primes[j]) == 0)
77				break;
78			j++;
79		}
80		if (rem)
81			primes[num_primes++] = pc;
82	}
83}
84
85/* factor:  prepare a list of prime factors of val.
86   The last number may not be a prime factor is the list is not
87   long enough. */
88
89void
90factor(val, fact_list, fact_size, num_fact)
91	long val;
92	long *fact_list;
93	int fact_size;
94	int *num_fact;
95{
96	int i;
97
98	/* Check to make sure we have enough primes. */
99	build_primes(val);
100
101	i = 0;
102	*num_fact = 0;
103	while (*num_fact < fact_size-1 && val > 1 && i < num_primes) {
104		/* Find the next prime that divides. */
105		while (i < num_primes && val % primes[i] != 0) i++;
106
107		/* Put factors in array. */
108		while (*num_fact < fact_size-1 && i < num_primes &&
109		    val % primes[i] == 0) {
110			fact_list[(*num_fact)++] = primes[i];
111			val /= primes[i];
112		}
113	}
114	if (val > 1)
115		fact_list[(*num_fact)++] = val;
116}
117
118
119
120#include <stdio.h>
121#include <stdlib.h>
122
123int
124main(int argc, char **argv)
125{
126	long facts[30];
127	long val;
128	int i, nfact;
129	int arg;
130
131	if (argc < 2) {
132		fprintf (stderr, "usage: %s numbers\n", argv[0]);
133		exit(1);
134	}
135
136	/* Factor each arg! */
137	for (arg = 1; arg < argc; arg++) {
138
139		val = atol(argv[arg]);
140		factor (val, facts, 30, &nfact);
141
142		printf ("%ld:", val);
143		for (i = 0; i<nfact; i++)
144			printf (" %ld", facts[i]);
145		printf ("\n");
146
147	}
148
149	return 0;
150}
151#endif
152