src/snark/primfc.cpp

   1 /*
   2  ***********************************************************
   3  $SNARK_Header: S N A R K  1 4 - A PICTURE RECONSTRUCTION PROGRAM $
   4  $HeadURL: svn://dig.cs.gc.cuny.edu/snark/trunk/src/snark/primfc.cpp $
   5  $LastChangedRevision: 80 $
   6  $Date: 2014-07-01 21:01:54 -0400 (Tue, 01 Jul 2014) $
   7  $Author: agulati $
   8  ***********************************************************
   9
  10  THIS SUBROUTINE DETERMINES THE PRIMEFACTORIZATION
  11  OF N I.E.
  12  N=2**M * IPF(1)*...*IPF(NIPF)
  13  */
  14
  15 #include <cstdlib>
  16 #include <cstdio>
  17
  18 #include "blkdta.h"
  19 #include "uiod.h"
  20
  21 #include "primfc.h"
  22
  23 void primfc(INTEGER n, INTEGER* m, INTEGER* nipf, INTEGER* ipf, INTEGER mnipf)
  24 {
  25         INTEGER ns;
  26         INTEGER n2;
  27         INTEGER iup;
  28         INTEGER i;
  29
  30         // DETERMINE M
  31
  32         ns = n;
  33         *m = 0;
  34
  35         for (;;)
  36         {
  37                 n2 = ns / 2;
  38                 if ((2 * n2) != ns)
  39                         break;
  40                 ns = n2;
  41                 (*m)++;
  42         }
  43
  44         // DETERMINE OTHER PRIME FACTORS
  45
  46         (*nipf) = 0;
  47         iup = ns;
  48
  49         for (i = 3; i <= iup; i += 2)
  50         {
  51                 if (i > ns)
  52                         return;
  53                 for (;;)
  54                 {
  55                         n2 = ns / i;
  56                         if ((n2 * i) != ns)
  57                                 break;
  58                         ns = n2;
  59                         (*nipf)++;
  60                         if (*nipf > mnipf)
  61                         {
  62                                 fprintf(output,
  63                                                 "\n **** the number of prime factors in %d is too large (> %d)",
  64                                                 n, mnipf);
  65                                 fprintf(output, "\n **** program aborted\n");
  66                                 exit(1010);
  67                         }
  68                         ipf[*nipf - 1] = i;
  69                 }
  70         }
  71         return;
  72 }