src/factor.c

   1 /* factor -- print factors of n.  lose if n > 2^32.
   2    Copyright (C) 1986 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Written by Paul Rubin <phr@ocf.berkeley.edu>.  */
  19
  20 #include <stdio.h>
  21
  22 static void
  23 factor (n0)
  24      unsigned long n0;
  25 {
  26   register unsigned long n = n0, d;
  27
  28   if (n < 1)
  29     return;
  30
  31   while (n % 2 == 0)
  32     {
  33       printf ("\t2\n");
  34       n /= 2;
  35     }
  36   /* The exit condition in the following loop is correct because
  37      any time it is tested one of these 3 conditions holds:
  38       (1) d divides n
  39       (2) n is prime
  40       (3) n is composite but has no factors less than d.
  41      If (1) or (2) obviously the right thing happens.
  42      If (3), then since n is composite it is >= d^2. */
  43   for (d = 3; d * d <= n; d += 2)
  44     {
  45       while (n % d == 0)
  46         {
  47           printf ("\t%ld\n", d);
  48           n /= d;
  49         }
  50     }
  51   if (n != 1 || n0 == 1)
  52     printf ("\t%ld\n", n);
  53 }
  54
  55 static void
  56 do_stdin ()
  57 {
  58   char buf[1000];
  59
  60   for (;;)
  61     {
  62       /* FIXME: Use getline.  */
  63       if (fgets (buf, sizeof buf, stdin) == 0)
  64         exit (0);
  65       /* FIXME: Use strtoul.  */
  66       factor ((unsigned long) atoi (buf));
  67     }
  68 }
  69
  70 void
  71 main (argc, argv)
  72      int argc;
  73      char **argv;
  74 {
  75   if (argc == 1)
  76     do_stdin ();
  77   else if (argc == 2)
  78     factor ((unsigned) atoi (argv[1]));
  79   else
  80     {
  81       fprintf (stderr, "Usage: %s [number]\n", argv[0]);
  82       exit (1);
  83     }
  84   exit (0);
  85 }