distrib/utils/sysinst/factor.c

   1 /*      $NetBSD: factor.c,v 1.11 2000/12/22 10:12:12 mrg 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. All advertising materials mentioning features or use of this software
  18  *    must display the following acknowledgement:
  19  *      This product includes software developed for the NetBSD Project by
  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.
  24  *
  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
  27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  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  *
  37  */
  38
  39 /* Prototypes for strict prototyping. */
  40
  41 #include <sys/cdefs.h>
  42
  43 #include <stdio.h>
  44
  45
  46 /*
  47  * primes - prime table, built to include up to 46345 because
  48  * sqrt(2^31) = 46340.9500118415
  49  *
  50  * building the table instead of storing a precomputed table saves
  51  * about 19K of space on the binary image.
  52  */
  53
  54 #ifdef TESTING
  55 long primes[4800];
  56 int  num_primes = 2;
  57
  58 static void build_primes (long max);
  59 void factor (long val, long *fact_list, int fact_size, int *num_fact);
  60
  61 static void
  62 build_primes(max)
  63         long max;
  64 {
  65         long pc;
  66         int j;
  67         long rem;
  68
  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;
  75
  76         for (pc = primes[num_primes-1]; pc < 46345 && pc*pc <= max; pc+=2) {
  77                 j = 0;
  78                 rem = 1;
  79                 while (j < num_primes && primes[j] * primes[j] <= pc) {
  80                         if ((rem = pc % primes[j]) == 0)
  81                                 break;
  82                         j++;
  83                 }
  84                 if (rem)
  85                         primes[num_primes++] = pc;
  86         }
  87 }
  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
  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;
  99 {
 100         int i;
 101
 102         /* Check to make sure we have enough primes. */
 103         build_primes(val);
 104
 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. */
 109                 while (i < num_primes && val % primes[i] != 0) i++;
 110
 111                 /* Put factors in array. */
 112                 while (*num_fact < fact_size-1 && i < num_primes &&
 113                     val % primes[i] == 0) {
 114                         fact_list[(*num_fact)++] = primes[i];
 115                         val /= primes[i];
 116                 }
 117         }
 118         if (val > 1)
 119                 fact_list[(*num_fact)++] = val;
 120 }
 121
 122
 123
 124 #include <stdio.h>
 125 #include <stdlib.h>
 126
 127 int
 128 main(int argc, char **argv)
 129 {
 130         long facts[30];
 131         long val;
 132         int i, nfact;
 133         int arg;
 134
 135         if (argc < 2) {
 136                 fprintf (stderr, "usage: %s numbers\n", argv[0]);
 137                 exit(1);
 138         }
 139
 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         }
 152
 153         return 0;
 154 }
 155 #endif