Annotation of src/distrib/utils/sysinst/factor.c, Revision 1.12
1.12 ! christos 1: /* $NetBSD: factor.c,v 1.11 2000/12/22 10:12:12 mrg Exp $ */
1.1 phil 2:
3: /*
1.2 phil 4: * Copyright 1997 Piermont Information Systems Inc.
5: * All rights reserved.
1.1 phil 6: *
1.2 phil 7: * Written by Philip A. Nelson for Piermont Information Systems Inc.
1.1 phil 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. All advertising materials mentioning features or use of this software
18: * must display the following acknowledgement:
1.10 cgd 19: * This product includes software developed for the NetBSD Project by
1.2 phil 20: * Piermont Information Systems Inc.
21: * 4. The name of Piermont Information Systems Inc. may not be used to endorse
22: * or promote products derived from this software without specific prior
23: * written permission.
1.1 phil 24: *
1.2 phil 25: * THIS SOFTWARE IS PROVIDED BY PIERMONT INFORMATION SYSTEMS INC. ``AS IS''
26: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.1 phil 27: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.2 phil 28: * ARE DISCLAIMED. IN NO EVENT SHALL PIERMONT INFORMATION SYSTEMS INC. BE
29: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
35: * THE POSSIBILITY OF SUCH DAMAGE.
36: *
1.1 phil 37: */
38:
1.8 phil 39: /* Prototypes for strict prototyping. */
40:
1.9 mrg 41: #include <sys/cdefs.h>
42:
43: #include <stdio.h>
44:
1.1 phil 45:
46: /*
1.2 phil 47: * primes - prime table, built to include up to 46345 because
48: * sqrt(2^31) = 46340.9500118415
1.1 phil 49: *
1.2 phil 50: * building the table instead of storing a precomputed table saves
51: * about 19K of space on the binary image.
1.1 phil 52: */
53:
1.12 ! christos 54: #ifdef TESTING
1.4 cjs 55: long primes[4800];
1.2 phil 56: int num_primes = 2;
1.1 phil 57:
1.12 ! christos 58: static void build_primes (long max);
! 59: void factor (long val, long *fact_list, int fact_size, int *num_fact);
! 60:
1.9 mrg 61: static void
62: build_primes(max)
63: long max;
1.2 phil 64: {
65: long pc;
66: int j;
67: long rem;
68:
1.4 cjs 69: /*
70: * Initialise primes at run-time rather than compile time
71: * so it's put in bss rather than data.
72: */
73: primes[0] = 2;
74: primes[1] = 3;
1.6 phil 75:
1.5 phil 76: for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) {
1.2 phil 77: j = 0;
78: rem = 1;
1.9 mrg 79: while (j < num_primes && primes[j] * primes[j] <= pc) {
1.2 phil 80: if ((rem = pc % primes[j]) == 0)
81: break;
82: j++;
83: }
84: if (rem)
85: primes[num_primes++] = pc;
86: }
87: }
1.1 phil 88:
89: /* factor: prepare a list of prime factors of val.
90: The last number may not be a prime factor is the list is not
91: long enough. */
92:
1.9 mrg 93: void
94: factor(val, fact_list, fact_size, num_fact)
95: long val;
96: long *fact_list;
97: int fact_size;
98: int *num_fact;
1.1 phil 99: {
100: int i;
101:
1.2 phil 102: /* Check to make sure we have enough primes. */
103: build_primes(val);
104:
1.1 phil 105: i = 0;
106: *num_fact = 0;
107: while (*num_fact < fact_size-1 && val > 1 && i < num_primes) {
108: /* Find the next prime that divides. */
1.2 phil 109: while (i < num_primes && val % primes[i] != 0) i++;
1.1 phil 110:
111: /* Put factors in array. */
112: while (*num_fact < fact_size-1 && i < num_primes &&
1.9 mrg 113: val % primes[i] == 0) {
1.2 phil 114: fact_list[(*num_fact)++] = primes[i];
115: val /= primes[i];
1.1 phil 116: }
117: }
118: if (val > 1)
1.2 phil 119: fact_list[(*num_fact)++] = val;
1.1 phil 120: }
121:
1.8 phil 122:
123:
124: #include <stdio.h>
125: #include <stdlib.h>
126:
1.7 jonathan 127: int
128: main(int argc, char **argv)
1.1 phil 129: {
130: long facts[30];
131: long val;
132: int i, nfact;
1.6 phil 133: int arg;
1.2 phil 134:
135: if (argc < 2) {
1.6 phil 136: fprintf (stderr, "usage: %s numbers\n", argv[0]);
1.2 phil 137: exit(1);
138: }
1.1 phil 139:
1.6 phil 140: /* Factor each arg! */
141: for (arg = 1; arg < argc; arg++) {
142:
143: val = atol(argv[arg]);
144: factor (val, facts, 30, &nfact);
145:
146: printf ("%ld:", val);
147: for (i = 0; i<nfact; i++)
148: printf (" %ld", facts[i]);
149: printf ("\n");
150:
151: }
1.1 phil 152:
1.6 phil 153: return 0;
1.1 phil 154: }
155: #endif
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to factor.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / distrib / utils / sysinst